Error-Correcting Graph Codes

In this paper, we define, study, and construct Error-Correcting Graph Codes. An error-correcting graph code of distance 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 n vertices in order to reach some other graph in C. This is a natural graph generalization of the standard Hamming distance error-correcting codes for binary strings. We show: 1. Combinatorial results determining the optimal rate vs distance tradeoff nonconstructively. 2. A connection to rank-metric codes, enabling some simple and some involved constructions achieving certain positive rates and distances. 3. 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. 4. Graph code analogues of dual-BCH codes, yielding large codes with distance = 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 a desired property. Error-correcting graph codes are a particularly interesting instantiation of this concept.