Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality
Abstract
We study linear codes whose coordinates are the ordinary edges and self-loops of complete undirected graphs; 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, together with a general ordinary-edge framework that isolates the remaining loop-completion problem. When $2$ is primitive modulo an odd prime n, a binary multi-slope construction corrects every ρ-node erasure for 2≤ρ<n, with redundancy ρn−(ρ−1) in the range 2≤ρ≤(n+1)/2. Returning to arbitrary prime powers, we derive exact generating transforms and inclusion--exclusion formulas for node-metric ball volumes, fixed-radius asymptotics, and packing, existence, and covering bounds. Finally, for the complementary clique-erasure metric, we obtain an exact weight enumerator and a Singleton-optimal node--clique duality.
Related
- Plotkin-Like Bound and Explicit Function-Correcting Code Constructions for Lee Metric Channels
- Error-Correcting Weakly Constrained Codes: Constructions and Achievable Rates
- Generalized Function-Correcting Partition Codes: Bounds and constructions
- Constructions of complete permutations over 𝔽qn
- Multiple-Function Approximated Coded Computing: Constructions and Error Bounds
BibTeX
@misc{zabokritskiy2026binary,
title = {{Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality}},
author = {Aryeh Lev Zabokritskiy},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.01474},
eprint = {2609.01474},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.01474},
}
RIS
TY - UNPB
TI - Binary Multiple-Node-Erasure-Correcting Codes over Complete Graphs: Constructions, q-Ary Metric Balls, and Duality
AU - Aryeh Lev Zabokritskiy
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2609.01474
UR - https://arxiv.org/abs/2609.01474
AB - We study linear codes whose coordinates are the ordinary edges and self-loops of complete undirected graphs; 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, together with a general ordinary-edge framework that isolates the remaining loop-completion problem. When $2$ is primitive modulo an odd prime n, a binary multi-slope construction corrects every ρ-node erasure for 2≤ρ<n, with redundancy ρn−(ρ−1) in the range 2≤ρ≤(n+1)/2. Returning to arbitrary prime powers, we derive exact generating transforms and inclusion--exclusion formulas for node-metric ball volumes, fixed-radius asymptotics, and packing, existence, and covering bounds. Finally, for the complementary clique-erasure metric, we obtain an exact weight enumerator and a Singleton-optimal node--clique duality.
ER -