Maximally recoverable codes are codes designed for distributed storage which combine quick recovery from single node failure and optimal recovery from catastrophic failure. Gopalan et al [SODA 2017] studied the alphabet size needed for such codes in grid topologies and gave a combinatorial characterization for it in graph-theoretic terms.
Consider a labeling of the edges of the complete bipartite graph $K_{n,n}$ whose labels are d-bit strings. Assume that the labeling satisfies the following constraint: for any simple cycle, the sum of the labels (modulo 2) over the cycle is always nonzero. Then, the alphabet size needed for maximally recoverable codes in an $n \times n$ grid is d bits.
Gopalan et al. showed that the minimal value of $d$ where this is possible is between (log n)^2 and $n \log n$, and asked for the minimal possible value. In this work, we resolve this problem and show that $d=\Theta(n)$. The upper bound is a simple recursive construction. Most of the work is in proving the lower bound. We do so by first relating the problem to the chromatic number of the Birkhoff polytope, and then giving tight bounds for the latter. This is done via a structure-vs-pseudorandomness approach combined with the representation theory of the symmetric group.
Joint work with Daniel Kane and Sankeerth Rao.