Title:Error-Correcting Graph Codes

Abstract:In this paper, we construct Error-Correcting Graph Codes. An error-correcting graph code of distance $\delta$ is a family $C$ of graphs on a common vertex set of size $n$, such that if we start with any graph in $C$, we would have to modify the neighborhoods of at least $\delta n$ vertices in order to obtain some other graph in $C$. This is a natural graph generalization of the standard Hamming distance error-correcting codes for binary strings. Yohananov and Yaakobi were the first to construct codes in this metric, constructing good codes for $\delta < 1/2$, and optimal codes for a large-alphabet analogue. We extend their work by showing
1. Combinatorial results determining the optimal rate vs. distance trade-off nonconstructively.
2. Graph code analogues of Reed-Solomon codes and code concatenation, leading to positive distance codes for all rates and positive rate codes for all distances.
3. Graph code analogues of dual-BCH codes, yielding large codes with distance $\delta = 1-o(1)$. This gives an explicit ''graph code of Ramsey graphs''.
Several recent works, starting with the paper of Alon, Gujgiczer, Körner, Milojević, and Simonyi, have studied more general graph codes; where the symmetric difference between any two graphs in the code is required to have some desired property. Error-correcting graph codes are a particularly interesting instantiation of this concept.