Error-Correcting Graph Codes
<|reference_start|>Error-Correcting Graph Codes: 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\"orner, Milojevi\'c, 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.<|reference_end|>
@article{kopparty2024error-correcting,
    title={Error-Correcting Graph Codes},
    author={Swastik Kopparty, Aditya Potukuchi, and Harry Sha},
    journal={arXiv preprint arXiv:2406.13867},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.13867},
    primaryClass={cs.IT cs.DM math.CO math.IT}
}