Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.
Tom: We're looking at the paper: "Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs".
Jane: Here's the gist of the paper. Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality studies linear codes whose coordinates are ordinary edges and self-loops of complete undirected graphs, where a node erasure removes all coordinates incident with a failed vertex The construction results are binary For triple-node erasures, we extend the published cyclic construction by allowing a suitable cyclic check slope to depend on the prime graph length An explicit determinant test proves that one of three fixed slope choices works at infinitely many prime lengths, unconditionally, and gives redundancy 3n−2, one bit above the graph Singleton bound We also give Singleton-optimal triple-node codes at n = 6, 8, 10, 12 Code Construction and Bounds The paper develops constructions for linear graph codes over complete graphs where node erasure is modeled by removing all incident coordinates.
Tom: The core construction is binary, involving cyclic, multi-slope, and optimal-completion sections.
Jane: For a prime n ≥ 5 and λ primitive modulo n, the code C3(λ) corrects every three-node erasure if and only if the set of points Γn,λ is an n-arc.
Tom: The rank of the parity-check matrix for this construction is 3n−2.
Paper summary: Jane: So to wrap up what we just heard about "Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, qAry Metric Balls, and Duality", the main claim is that they've developed binary linear codes whose coordinates are the edges and self-loops of a complete undirected graph.
Tom: The thesis is that they can handle node erasures—where failing a vertex removes all incident coordinates—and their construction results are binary >
Lu: They extend an existing cyclic construction by allowing the check slope to depend on the prime length of the graph, and an explicit determinant test proves one of three fixed slope choices works for infinitely many prime lengths unconditionally >
Meng: So they’re not just giving a formula; they're proving that there's a family of solutions that works for almost all possible graph sizes, as long as the prime length is right >
Jane: And for triple-node erasures specifically, they achieve redundancy 3n minus two which is one bit above the graph Singleton bound > <ref:2609.01474#pg1,one bit above the graph Singleton bound>
Lalam: This code construction has some implications because it separates the local cyclic-minor condition from a primitive root condition, and they use Heath-Brown’s three integer primitive root theorem to show that this allows for an unconditional infinite set of admissible prime lengths >
Tom: That means we can always find an infinite set of prime numbers where this specific construction works without needing any extra assumptions about the graph size >
Jane: And they also pinpoint specific sizes, like n equals six, eight, ten, and twelve where they get Singleton-optimal triple-node codes >
Lu: So it’s a combination: an infinite family of prime lengths plus specific optimal solutions for certain small graph sizes >
Meng: From a deployment standpoint, that’s good because it gives us some concrete targets for what works well in this hard area of error correction >
Tom: So the core contribution is establishing this construction framework and showing how it isolates the remaining loop-completion problem so we can tackle it systematically >
Conclusion: Jane: Looking at the paper "Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, qAry Metric Balls, and Duality", what does this all mean for us in plain terms?
Tom: It means we have a more robust way to design codes for systems where errors happen on specific geometric structures like graphs >
Lu: Specifically, it gives us tools to correct failures when the failure pattern is related to node erasures on these complete graph settings, and we can achieve better redundancy than previously known bounds >
Meng: For someone shipping models, it means having a theoretical foundation for codes that can handle those specific types of faults efficiently at scale >
Jane: It moves us away from just looking at dimension alone; the ball-volume calculation explains why simple dimension arguments miss a polynomial factor in the size of these correction spaces >
Lalam: And they showed that this construction provides an arithmetic contribution by verifying all four hundred sixteen exact rank checks, which is a lot of concrete evidence to back up the claims made >
Tom: So ultimately, it’s about providing a constructive method for building codes for these graph erasure problems and giving us better bounds on how powerful those codes can be >
Department of Computer Science, Tel-Hai University of Kiryat Shmona in the Galilee · MIGAL–Galilee Research Institute
cs.IT, math.CO, math.IT
Submitted: 2026-09-01
Updated: 2026-11-10
Comments: 44 pages
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Importance score: 87/100
The gist: Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls…
Key concepts
- Node Erasure
- This is an error model where a specific vertex (node) in the complete graph is removed. In this coding scheme, removing a node causes all coordinates (edges or self-loops) connected to that node to be considered erased, meaning they cannot be used for decoding.
- Singleton Bound
- This is a fundamental limit on how many errors a code can correct relative to its length. The paper achieves redundancy levels very close to this bound, specifically reaching $3n-2$ for triple-node erasures and $3n-3$ in some cases, indicating highly efficient error correction.
- Metric Ball Analysis
- This involves studying the geometric properties of the code space using a specific distance metric related to node erasures. By analyzing the volume of 'balls' around points in this space, researchers can determine exact bounds and understand how efficiently the code covers potential erasure patterns.
- Node-Clique Duality
- This is a relationship between two different ways of viewing error correction problems. It states that a code can correct erasures related to cliques (groups of connected nodes) if and only if its minimum clique distance meets a specific threshold, linking structural properties to error-correcting power.
Terminology
Summary
Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality studies linear codes whose coordinates are ordinary edges and self-loops of complete undirected graphs, where a node erasure removes all coordinates incident with a failed vertex The construction results are binary For triple-node erasures, we extend the published cyclic construction by allowing a suitable cyclic check slope to depend on the prime graph length An explicit determinant test proves that one of three fixed slope choices works at infinitely many prime lengths, unconditionally, and gives redundancy 3n−2, one bit above the graph Singleton bound We also give Singleton-optimal triple-node codes at n = 6, 8, 10, 12
Code Construction and Bounds
The paper develops constructions for linear graph codes over complete graphs where node erasure is modeled by removing all incident coordinates. The core construction is binary, involving cyclic, multi-slope, and optimal-completion sections. p. 1 For a prime n ≥ 5 and λ primitive modulo n, the code C3(λ) corrects every three-node erasure if and only if the set of points Γn,λ is an n-arc. p. 9 The rank of the parity-check matrix for this construction is 3n−2. p. 6 Furthermore, for every 2 ≤ ρ < n, the code C MSρ corrects every set of at most ρ node erasures with redundancy ρn − (ρ − 1) when 2 is primitive modulo n. p. 0
Metric Ball Analysis and Duality
The paper investigates the metric properties of these codes, deriving exact loop-conditioning transforms for the node-weight enumerator. The volume of a radius-t node ball in the looped q-ary graph space has an asymptotic form of n t/q tn−(t 2). p. 3 For the complementary cliqueerasure metric, an exact weight enumerator is obtained, and a Singleton-optimal node–clique duality is established. p. 0 The duals of the optimal double-node-erasure codes form an unconditional infinite family of optimal binary (n − 2)-clique-erasure codes for every odd prime length covered by that construction. p. 3
Finite Field Constructions and Optimality
The paper constructs explicit binary triple-node codes with the Singleton redundancy 3n − 3 for n = 6, 8, 10, and 12. This is achieved by realizing classical Delsarte–Goethals Frobenius layers as columns indexed by the ordinary edges of an affine frame. p. 2 The uniform Moore edge skeleton theorem shows that for every 2 ≤ ρ ≤ n, the erased-edge block has full column rank. p. 3 The exact finite completions at n = 6, 8, 10, 12 demonstrate that the obstruction in the published cyclic parity-check matrix is not an obstruction to optimal triple-node codes themselves. p. 6
Enumeration and Asymptotics
The paper develops two complementary counting routes for analyzing code bounds: conditioning on nonzero loops or viewing a ball as a union of failed-star coordinate subspaces. The exact Venn-profile formula provides an exact enumeration of the ball size. p. 3 For fixed q and t, the asymptotic volume is Bt = n t/q tn−(t 2) 1 + Oq,t(nq−n). p. 3 The packing and Gilbert bounds yield a random-linear redundancy at most ρ log q n + Oq,ρ(1) above Singleton for fixed ρ. p. 3
Complementary Metric and Duality
The complementary clique metric is introduced, where the distance between two words is the minimum number of vertices whose support lies in a clique. The node-clique duality theorem states that a code corrects every erasure of an induced clique on at most µ vertices if and only if its minimum clique distance is at least µ + 1. p. 6
Discussion and Open Problems
The central Singleton-optimal constructive problem remains to find an infinite family with redundancy 3n − 3. The remaining results separate three regimes that had previously been entangled. p. 0 The multi-slope family is uniform in the number of failed nodes and improves the Schmidt benchmark throughout the range 2 ≤ ρ ≤ (n + 1)/2 of Theorem 15. p. 2 The Moore theorem shows uniformly for every 2 ≤ ρ ≤ n that the Moore edge skeleton has maximum local rank on every failed set. p. 2 The ball-volume calculation explains why dimension-only arguments miss a polynomial factor. p. 3 p. 3
Computational Reproducibility
All computer-assisted verifications reported in this paper were carried out using exact arithmetic. The complete versioned verification package, including source code, certificate data, execution instructions, recorded outputs, and cryptographic checksums for every reported finite check is publicly archived in Zenodo.
Appendix A Proof of the Local Determinant Criterion
The proof of Lemma 6 involves tracking the kernel of the parity-check matrix on one failed triple. The final step shows that distinct elements of J∩im Lλ give distinct cosets and therefore distinct nonzero exterior classes Wy, hence distinct local codewords. p. 9
Appendix B Rank of the Primitive-Slope Check Matrix
The proof of Proposition 8 shows that the row rank is 3n − 2. The row dependence space has dimension 1 + L = ρ − 1, and hence rank H MSρ = ρn − (ρ − 1). p. 7
Appendix C Proof of the Multi-Slope Theorem
The proof of the correction assertion in Theorem 15 involves Frobenius descent to show that the product and Frobenius–Moore equations displayed there force w = 0.
Appendix D One-Bit Extension Criterion and Finite Obstructions
This appendix records a limitation of one particular improvement route. The obstruction concerns the published slope-two check space and is not an obstruction theorem for all of the primitive slopes in Theorem 13. p. 2
Appendix E Dual Weight Data and the Failure of a Univariate MacWilliams Transform
The witness shows that equal primal enumerators can have unequal dual enumerators. The orbit type of the support under vertex relabeling is needed to refine node weight by additional intersection data. p. 4
Acknowledgments
The author used OpenAI’s ChatGPT and Codex as assistive tools in developing and revising portions of the abstract, introduction, definitions, construction and metric sections, discussion, and appendices. The systems were used to generate candidate mathematical arguments, formulations, proof checks, and code. p. 5 The author assumes full responsibility for all statements, proofs, computations, citations, and code in this article. p. 3
References
[1] L. Yohananov and E. p. 0 p. 0 Yaakobi, “Codes for graph erasures,” IEEE Trans. p. 0 Inf. Theory, vol. 65, no. 9, pp. 5433–5453
[2] L. Yohananov, Y. p. 0 Efron, and E. Yaakobi, “Double and triple node-erasure-correcting codes over complete graphs,” IEEE Trans. p. 0 Inf. Theory, vol 66, no 7
[3] L. Yohananov and E. Yaakobi, “Codes over trees,” IEEE Trans. p. 1 Inf. Theory, vol 67, no 6
[4] A Barg, M. Schwartz, and L. Yohananov, “Storage codes on coset graphs with asymptotically unit rate,” Combinatorica, vol 44, no 6
[5] S. Kopparty, A. p. 1 p. 1 Potukuchi, and H. p. 1 p. 1 Sha, “Error-correcting graph codes,” in Proc. p. 1 16th Innovations in Theoretical Computer Science Conf. p. 0, vol 325
[6] Y. Chen, M. Cheraghchi, and N. p. 1 Shagrithaya, “Optimal erasure codes and codes on graphs”
[7] U. Mart´ınez-Pe˜nas, “Multilayer crisscross error and erasure correction,” Linear Algebra Appl., vol 728
[8] K.-U. Schmidt, “Symmetric bilinear forms over finite fields of even characteristic,” J. p. 2 Combin. Theory, Ser A, vol 117
[9] K.-U. Schmidt, “Quadratic and symmetric bilinear forms over finite fields and their association schemes,” Algebr. p. 2 Comb., vol 3, no 1
[10] P. Delsarte and J. p. 2-M. Goethals, “Alternating bilinear forms over GF(q)”
[11] J. A. Pinheiro, R. A. Machado, and M. Firer, “Combinatorial metrics: MacWilliams-type identities”
[12] D. R. Heath-Brown, “Artin’s conjecture for primitive roots” Quart. p. 3 J. Math., Oxford Ser (2), vol 37, no 1
[13] R. Gow and R. Quinlan, “Galois extensions and subspaces of alternating bilinear forms with special rank properties” Linear Algebra Appl. p. 2, vol 430, nos 8–9
[14] A. L. Zabokritskiy (Yohananov), “Exact verification companion to Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, qary Metric Balls, and Duality,” Zenodo, Software, ver. p. 0 1.0.1
[15] S. Yoshiara, “Dimensional dual hyperovals associated with quadratic APN functions” Innov. Incidence Geom. p. 8, vol 8
[16] W. M. Kantor and E. E. Shult, “Veroneseans, power subspaces and independence” Adv. p. 9 Geom., vol 13, no 3
[17] H.-A. Loeliger, “On the basic averaging arguments for linear codes” in Communications and Cryptography: Two Sides of One Tapestry, R. p. 1 E. Blahut, D. J. Costello, Jr., U. Maurer, and T. Mittelholzer, Eds., Boston, MA: Kluwer Academic
[18] L. Lov´asz, “On the ratio of optimal integral and fractional covers,” Discrete Math. p. 1, vol 13, no 4
[19] V. Chv´atal, “A greedy heuristic for the set-covering problem” Math. p. 3 Oper. Res., vol 4, no 3
[20] E. A. Bender, E. R. Canfield, and B. D. McKay, “The asymptotic number of labeled graphs with n vertices, q edges, and no isolated vertices” J. p. 4 Combin. Theory Ser A, vol 80
[21] L. Holzbaur, S. Puchinger, E. Yaakobi, and A Wachter-Zeh, “Correctable erasure patterns in product topologies” in Proc. p. 6 IEEE Int. Symp. Inf. Theory (ISIT), 2021
[25] S. Kopparty, A. Potukuchi, and H. Sha, “Error-correcting graph codes,” in Proc 16th Innovations in Theoretical Computer Science Conf. p. 0, vol 325
Pruning redundant reasoning tokens
The paper focuses on the low-redundancy regime of a fixed number of failures, retaining loop coordinates and studying exact finite geometry. The construction core—the cyclic, multi-slope, and optimal-completion sections together with their algebraic proofs—is binary. p. 1 The metric part involves the same failed-star coordinate sets becoming a subspace arrangement whose union is a node-metric ball. p. 1
How the training signal is built
The construction part involves a local column-independence problem for a parity-check matrix. The metric part leads to the duality problem where failed-star coordinate sets become a subspace arrangement defining a node-metric ball. p. 1 The construction relies on the local rank criterion for correcting node erasures. p. 3 The algebraic proof of Lemma 35 shows that the product and Frobenius–Moore equations force w = 0, leading to the vanishing of all checks.
Where the gains come from
The gains come from allowing a length-dependent choice from the fixed set of slopes to invoke Heath-Brown’s theorem and prove infinitude unconditionally. The new family has redundancy one above the graph Singleton value 3n−3, and two below the Schmidt benchmark value 3n. p. 2 The multi-slope construction saves ρ − 1 binary checks compared to the Schmidt benchmark. p. 2 The exact loop-completion certificates at n = 6, 8, 10, 12 establish Singleton optimality at these lengths. p. 0 The ball-volume calculation explains why dimension-only arguments miss a polynomial factor. The final results separate three regimes that had previously been entangled. p. 0 p. 0
The paper's contributions are arithmetic: after allowing the slope to be selected from three fixed integers, it proves infinitely many admissible prime lengths unconditionally. The exact arithmetic verification archive records all 416 exact rank checks. p. 3 The new family has the same redundancy and erasure capability as the 2020 construction, and its contribution is arithmetic. p. 3 The duals of the optimal triple-node completions in Section 4 give optimal (n − 3)-clique-erasure codes at n = 6, 8, 10, 12. p. 3 The exact odd-dependency certificates were produced and independently verified for the admissible sample lengths n = 5, 11, 13, and n = 19. p. 2 The final results separate three regimes that had previously been entangled.
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Improved code construction for binary multiple-node erasure correcting codes allows for explicit determination of redundant bits based on graph parameters, achieving redundancy 3n minus 2 over complete graphs. This system can construct Singleton-optimal triple-node codes at specific lengths like n = 6, 8, 10, and 12.
-
Enhanced combinatorial counting methods for node metric balls allow for the derivation of exact generating functions and inclusion exclusion formulas for ball volumes. This enables precise calculation of packing, existence, and covering bounds beyond asymptotic estimates.
-
A dual theory based on the star-clique partition provides a framework to relate optimal node-erasure codes to optimal clique-erasure codes. This allows researchers to derive unconditional infinite families of optimal binary clique-erasure codes from existing node-erasure constructions.
-
The multi-slope construction provides a uniform correction scheme for every 2 ≤ rho < n, improving the Schmidt benchmark redundancy gap by a factor dependent on the number of failures. This system can correct every ρ-node erasure with redundancy ρn minus (ρ − 1) in the range 2 ≤ ρ ≤ (n + 1)/2.
-
The uniform Moore edge skeleton theorem provides a method to construct an ordinary-edge matrix with full local rank for every failed set Q. This system can reduce the remaining loop-completion problem to a common quotient problem, leading to exact optimal triple-node codes at n = 6, 8, 10, and 12.
-
The projective refinement technique enables the calculation of exact bounds on ball volumes by recording all overlaps via Venn profiles. This allows for the computation of pair intersection bounds and yields explicit asymptotic formulas for fixed-radius as well as fixed q asymptotics.
-
The construction provides an exact verification package using polynomial certificates that reconstruct every failed triple from input data and check rank conditions in a binary manner. This system can independently verify the rank of the required parity-check matrix for a given set of failed vertices, ensuring no missed errors occur.
Sources
Related papers
- The Gaussian Multiuser Channel Capacity Region
- The mathematical landscape of partial information decomposition: A comprehensive review of properties and measures
- Analytically Characterized Optimal Power Control for Signal-Level-Integrated Sensing, Computing and Communication in Federated Learning
- Information Spectrum Methods for Multiple-Access Channels--Part I: epsilon-Capacity Regions in the Mixed Gaussian Case
- Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert--Varshamov Bound
- Second-Order Image Characterization with Distortion and Secrecy