{"id":"048d0212-f521-4773-b57e-00e0f8b3a659","arxiv_id":"1908.03513","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For any simple graph with adjacency matrix A, the code generated by [I_n|A] has minimum distance min_S(|S|+|von(S)|), and is self-dual exactly when A^2 equals the identity matrix over F2.","lead":"This paper turns a graph into a binary error-correcting code using the matrix [I|A], and gives a formula for the code's minimum distance in terms of odd-neighbor sets. It also states exactly when such codes are self-dual or doubly even, with examples from complete graphs, cycles, and strongly regular graphs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Theorem 3.12(b) is false: K1 joined with a 5-vertex graph yields d1+d2=4>3=d, so the join lower bound needs correction.","rationale":"The central results, especially the Theorem 2.9 minimum-distance formula and the self-duality characterizations in Theorems 3.1 and 3.3, appear correctly derived; the symmetry of A is explicitly assumed and does not introduce a hidden flaw into Theorem 2.9. The genuine defect is Theorem 3.12(b). Its proof's Case 2 incorrectly treats every vertex of V2 as lying in von(S) when |S1| is odd and |S2| is even, ignoring the parity contribution from S2. The error is consequential: the explicit counterexample satisfies all hypotheses and violates the conclusion. Because this false theorem is peripheral rather than one of the abstract's central claims, the paper should remain conditional pending a correction or removal of Theorem 3.12(b), which matches the reader's verdict. I only partially agree with the reader's stated weakest assumption: the explicit symmetry assumption is benign, while the join theorem is falsifiable and false.","tokens_in":10901,"tokens_out":30037,"duration_ms":272476,"concrete_test":"Verify the counterexample by computing d1, d2, and d for Γ1 = K1 and Γ2 with adjacency matrix rows 01110, 10001, 10010, 10101, 01010 using Theorem 2.9 or a direct parity-check search. The expected values are d1 = 1, d2 = 3, and d = 3 for the join, where S = {center, 1, 2} realizes |S| + |von(S)| = 3 while no weight-2 codeword exists. This directly contradicts the claimed d1 + d2 ≤ d. An exhaustive check over all graph pairs on at most six vertices will reproduce this failure.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The weakest point is not the explicit symmetry assumption but the proof of Theorem 3.12(b). In Case 2 (|S1| odd, |S2| even) the proof asserts 'von(S) is the union of V2 and von(S1) in Γ1'. This is false: a vertex w in V2 is adjacent to all of S1 (odd) and also to its neighbors in S2; since |S2| is even, w is in von(S) iff w is not in von2(S2). The correct expression is von(S) = von1(S1) ∪ (V2 \\ von2(S2)). The proof uses the larger set, invalidating the inequality. The statement itself is false: take Γ1 = K1 (d1 = 1) and Γ2 the 5-vertex graph with edges 12, 13, 14, 25, 34, 45. For Γ2, Theorem 2.9 gives d2 = 3 (e.g. S = {2} has value 1 + |{1,5}| = 3, and no subset gives less). In the join, S = {c,1,2} has |S| = 3 and von(S) = ∅ because the pair {1,2} has von2({1,2}) = V2 and the center contributes even adjacency, so d ≤ 3; no degree-1 vertex and no duplicate vertices in the join force d = 3. Thus d1 + d2 = 4 > 3 = d, contradicting 3.12(b).","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies binary linear codes generated by matrices of the form [I_n | A], where A is the adjacency matrix of a simple graph on n vertices. The main results are a combinatorial formula for the minimum distance of such codes in terms of odd-neighborhood sets (Theorem 2.9), necessary and sufficient conditions for self-duality and Type I/II status in terms of graph degrees and common-neighbor parities (Theorems 3.1, 3.3, 3.8), applications to complete graphs and strongly regular graphs, and a final section analyzing the effect of the join operation on minimum distance and self-duality.","tokens_in":11222,"tokens_out":3455,"duration_ms":34592,"significance":"If the main results hold, the paper provides a clean dictionary between graph-theoretic quantities and code parameters: minimum distance becomes an extremal problem over subsets S involving |S|+|von(S)|, and self-duality is exactly the condition A^2 = I_n over F_2. Theorems 2.9, 3.1, 3.3, and 3.8 are derived carefully from standard parity-check theory and appear correct. However, the join section contains a false theorem (Theorem 3.12(b)) with an erroneous proof, so the paper is not yet acceptable in its current form.","major_comments":[{"comment":"Theorem 3.12(b) is false as stated. A concrete counterexample is given by taking Γ1 = K1 and Γ2 the 5-vertex graph with edges 12, 13, 14, 25, 34, 45. For Γ2, one computes d2 = 3 via Theorem 2.9 (e.g., S = {2} gives |S|+|von(S)| = 3 and no subset gives less), while d1 = 1. In the join Γ1 ∨ Γ2, the subset S = {c,1,2} (where c is the center of K1) has |S| = 3 and von(S) = ∅, because the pair {1,2} satisfies von2({1,2}) = V2 and the center contributes even adjacency. Since the join has no isolated vertices and no duplicate vertices, d = 3. Thus d1 + d2 = 4 > 3 = d, contradicting the claimed inequality d1 + d2 ≤ d. The error in the proof occurs in Case 2, where the authors assert that von(S) is the union of V2 and von1(S1). The correct formula for |S1| odd and |S2| even is von(S) = von1(S1) ∪ (V2 \\ von2(S2)), because a vertex w in V2 sees |S1| odd neighbors in S1 and has odd adjacency to S2 exactly when w ∈ von2(S2); the total parity is odd exactly when w ∉ von2(S2). The proof uses the larger set, invalidating the inequality. The theorem should be corrected or its statement revised to a true lower bound using the correct von(S) expression.","section":"Section 3, Theorem 3.12(b) and its proof"},{"comment":"The statement of Theorem 3.11(c) says that when exactly one of n1 and n2 is divisible by 4, C([I_{n1+n2}|A]) is Type I. The proof argues that n1+n2 ≡ 2 (mod 4) and hence the code length is 2(n1+n2) ≡ 4 (mod 8), which is not a multiple of 8, so the code cannot be Type II. This argument is correct, but it assumes the code is self-dual; if the preconditions of the theorem are not explicitly stated, the reader may be confused. Please state explicitly that (c) concerns codes that are already known to be self-dual from Theorem 3.10, or add the self-duality condition to the theorem statement.","section":"Section 3, Theorem 3.11(c)"}],"minor_comments":[{"comment":"The abstract and first page contain several OCR-style typos: 'in particu lar', 'a dding', 'have made it suitable', 'needed throughout' should be cleaned up. The sentence 'we can bring the generator matrix G into a standard form [I_k|A]' silently assumes Gaussian elimination over F_2; this is standard but could be said explicitly.","section":"Abstract and page 1"},{"comment":"In the proof of Theorem 2.8, Case 2, the equation 'A1 + A2 + · · · + Ak + ei2 + · · · + eid−k ≡ 0 (mod 2)' appears to contain a typo: the term ei1 is missing on the left-hand side. It should read 'A1 + A2 + · · · + Ak + ei1 + ei2 + · · · + eid−k ≡ 0 (mod 2)' for the subsequent conclusion to hold.","section":"Theorem 2.8 proof"},{"comment":"Observation 2.15 is phrased as a remark about an apparent pattern; if the authors intend the observation to support Conjecture 2.16, they should either prove it for the listed cases or label it as an empirical observation. The phrase 'At least one of these two properties seems to hold' is informal for a research paper.","section":"Observation 2.15 and Conjecture 2.16"},{"comment":"Reference [15] is cited for the [I_n|A] construction, but the connection to isoduality in the introduction (item 3) is not attributed. It would improve the exposition to state explicitly where the isoduality observation comes from, whether from the present paper or from previous work.","section":"References"}],"recommendation":"major_revision","confidential_remarks":"The paper's main construction and the core theorems (2.9, 3.1, 3.3, 3.8) appear sound and are reasonably self-contained. The false Theorem 3.12(b) is a genuine mathematical error, but it is localized to the join section and should be fixable by correcting the von(S) formula and the resulting inequality. I therefore recommend major revision rather than rejection, provided the authors address the counterexample and correct the theorem."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The genuinely new thing here is Theorem 2.9: for the binary code generated by [I_n|A], the minimum distance equals min over nonempty S of (|S| + |von(S)|). That turns code distance into a graph quantity you can compute from odd-neighborhoods, and it is derived cleanly from the parity-check matrix. The self-dual and Type II characterizations (Theorems 3.1 and 3.3) are also correct: self-duality is exactly A^2 = I over F2, which for simple graphs means all degrees odd and common-neighbor counts even; Type II requires in addition every degree congruent to 3 mod 4. These are useful, properly attributed to the [I|A] construction from Tonchev, and the examples for complete graphs and strongly regular graphs check out.\n\nThe soft spot is real and larger than a typo. Theorem 3.12(b) is false. In the proof for the join Γ1∨Γ2, Case 2 claims that when |S1| is odd and |S2| even, von(S) = von1(S1) ∪ V2. That is wrong. A vertex in V2 sees all of the odd set S1 plus its neighbors in S2, so its parity flips exactly when it is not in von2(S2). The correct expression is von1(S1) ∪ (V2 \\ von2(S2)). With that, the claimed inequality d1+d2 ≤ d does not follow. The stress-test example—K1 joined to the 5-vertex graph with edges 12,13,14,25,34,45—has d1=1, d2=3, but the join has minimum distance 3, so d1+d2=4 > 3. I checked the von computations and they are right. This invalidates part of the join discussion, but it does not infect the earlier sections. The main formula, the self-duality characterizations, and the examples stand.\n\nOne small note: the paper asserts Conjecture 2.16 without much evidence, but that is clearly labeled as a conjecture, so no problem.\n\nOverall, this paper deserves a serious referee. The central formula and the graph-theoretic criteria are a solid contribution to the coding-theory-from-graphs literature. The join section needs to be reworked or the false theorem removed. I would send it out for review, telling the authors the join proof has a counterexample and asking for a corrected version.","headline":"The paper's main distance formula and self-duality characterizations are correct and worth knowing; the join section contains a false theorem that needs fixing before this can be accepted.","tokens_in":11763,"tokens_out":4879,"would_cite":true,"duration_ms":43612,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["94B05","94B25"],"pacs":[],"model":"deepseek-v4-flash","headline":"For any simple graph, the binary code generated by [I_n|A] has minimum distance equal to the smallest value of |S|+|von(S)| over nonempty vertex subsets S.","keywords":["self-dual codes","isodual codes","adjacency matrix","minimum distance","odd neighborhood","Type II codes","strongly regular graphs","graph join"],"falsifier":"Enumerate all simple graphs on, say, six vertices, compute the code generated by [I_6|A], and compare its brute-force minimum distance with min over nonempty S of (|S|+|von(S)|); any mismatch would disprove Theorem 2.9. Alternatively, search for a graph with $A^{2}$ congruent to I_n mod 2 whose code contains a codeword of weight not divisible by 4, which would contradict Theorem 3.3.","tokens_in":10688,"feed_emoji":"🔗","tokens_out":4350,"duration_ms":37626,"temperature":0.7,"pith_summary":"This paper proves that every simple undirected graph gives a binary linear code through the generator matrix [I_n|A], where A is the adjacency matrix, and that the coding-theoretic invariants of that code are visible in the graph. The core result is an exact formula: the code's minimum distance equals the minimum over nonempty vertex sets S of |S| + |von(S)|, where von(S) is the set of vertices with an odd number of neighbors in S. Because A is symmetric, the parity-check matrix is a column permutation of the generator matrix, so every such code is isodual. The paper also characterizes self-duality as $A^{2}$ = I_n over F2, which translates into 'every vertex has odd degree and every pair of vertices has even common-neighbor count,' and Type II self-duality as every vertex having degree 3 mod 4. These graph-theoretic translations turn questions about self-dual codes into questions about graph structure and generate many explicit examples, including extremal codes from complete graphs.","feed_headline":"Graph adjacency matrix gives exact code distance formula","feed_subtitle":"For [I_n|A] codes, minimum distance is min |S|+|von(S)|, and A^2=I_n decides self-duality.","key_machinery":"The odd-neighborhood operator von(S) = {v : |N(v) intersect S| is odd} on the vertex set of Gamma, together with the binary adjacency matrix A. It carries the argument because a sum of columns of A has ones exactly on von(S); therefore the minimal linear dependencies of [A|I_n] are in bijection with pairs (S, von(S)). This yields the minimum-distance formula and, through the symmetry A = A^T, the isoduality and self-duality criteria.","core_discovery":"The central discovery is a dictionary between a code C with generator [I_n|A] and the graph Gamma whose adjacency matrix is A. Theorem 2.9 states that d(C) = min over nonempty S of V of (|S| + |von(S)|), where von(S) is the odd-neighborhood of S. The proof identifies minimally dependent columns of the parity-check matrix [A|I_n] with unions of columns indexed by S and by von(S). Theorem 3.1 then characterizes self-duality of C by $A^{2}$ being congruent to I_n mod 2, equivalently all vertices have odd degree and all pairs of distinct vertices have an even number of common neighbors; Theorem 3.3 adds that the code is Type II exactly when all degrees are 3 mod 4. The paper applies these conditions to complete graphs, strongly regular graphs, and joins, producing families of self-dual, Type I and Type II codes with known parameters.","pith_inferences":["If the minimum-distance formula is correct, it gives an efficient combinatorial way to compute or bound the distance of [I_n|A] codes without enumerating codewords, since it reduces the computation to a search over 2^n vertex subsets.","The same von(S) operator may transfer to other graph-derived matrices, such as incidence matrices or signed adjacency matrices, by replacing 'odd neighborhood' with the appropriate parity condition; the paper does not explore those settings.","The paper's Conjecture 2.16, that a minimizing set S satisfies S = von(S) or S intersect von(S) is empty, could be tested exhaustively on all graphs up to seven or eight vertices; if true it would simplify the search for minimum-weight codewords."],"forward_implications":["Every graph isomorphism class yields a code whose minimum distance is a graph invariant under the formula, even when the codes themselves are not identical.","Any graph with all degrees odd and pairwise even common-neighbor counts produces a self-dual [2n,n] code, and if degrees are 3 mod 4 the code is doubly even.","Complete graphs K_n with n even give self-dual [2n,n,4] codes; K_4 and K_8 give extremal Type II codes and K_6 an extremal Type I code.","The join of two graphs whose codes are self-dual is again self-dual, with type rules depending on the sizes modulo 4.","For any graph, d(C) is at most rk2(A)+1, giving a lower bound on the 2-rank of a graph."],"supporting_citations":[{"why":"Introduces the construction of codes from adjacency matrices that this paper extends to [I_n|A].","marker":"[15]"},{"why":"Supplies the shadow bounds that define extremal Type I and Type II codes used in the examples.","marker":"[13]"},{"why":"Studies linear dependencies among columns of graph matrices, which underlies the von(S) characterization.","marker":"[11]"},{"why":"Provides the 2-rank framework used in the upper bound d(C) <= rk2(A)+1.","marker":"[1]"}],"fun_headline_variants":["Odd-neighborhood formula gives exact code distance","Graph parity decides Type I and II self-dual codes","Self-dual codes from adjacency matrix parity","Code distance from graph odd neighborhoods","Graph conditions yield self-dual code types"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The argument assumes A is the symmetric adjacency matrix of a simple undirected graph, so that the parity-check matrix is [A|I_n]; for directed or asymmetric adjacency, the isodual structure and the von(S) formula would need separate treatment.","fun_headline_variants_meta":{"raw":{"variants":["Odd-neighborhood formula gives exact code distance","Graph parity decides Type I and II self-dual codes","Self-dual codes from adjacency matrix parity","Code distance from graph odd neighborhoods","Graph conditions yield self-dual code types"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000228,"raw_usage":{"total_tokens":1405,"prompt_tokens":803,"completion_tokens":602,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":419,"completion_tokens_details":{"reasoning_tokens":535}},"tokens_in":419,"tokens_out":602,"duration_ms":6509,"temperature":1.0,"reasoning_tokens":535,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T14:13:24.230636+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all simple graphs on, say, six vertices, compute the code generated by [I_6|A], and compare its brute-force minimum distance with min over nonempty S of (|S|+|von(S)|); any mismatch would disprove Theorem 2.9. Alternatively, search for a graph with $A^{2}$ congruent to I_n mod 2 whose code contains a codeword of weight not divisible by 4, which would contradict Theorem 3.3.","supporting_citations":[{"cited_title":"Rank-3 Graphs, Block Designs, and Codes with Un equal Symbol Protec- tion","cited_arxiv_id":null,"evidence_quote":"Introduces the construction of codes from adjacency matrices that this paper extends to [I_n|A]."},{"cited_title":"Shadow Bounds for Self Dual Codes","cited_arxiv_id":null,"evidence_quote":"Supplies the shadow bounds that define extremal Type I and Type II codes used in the examples."},{"cited_title":"Classes of graphs with minimum skew ra nk 4","cited_arxiv_id":null,"evidence_quote":"Studies linear dependencies among columns of graph matrices, which underlies the von(S) characterization."},{"cited_title":"Switched symplectic graphs and their 2 -ranks","cited_arxiv_id":null,"evidence_quote":"Provides the 2-rank framework used in the upper bound d(C) <= rk2(A)+1."}],"review_version":1}