Tighter Bounds on the Independence Number of the Birkhoff Graph

Abstract

The Birkhoff graph ${\mathcal{B}}_n$ is the Cayley graph of the symmetric group $S_n$, where two permutations are adjacent if they differ by a single cycle. Our main result is a tighter upper bound on the independence number $\alpha ({\mathcal{B}}_n)$ of ${\mathcal{B}}_n$, namely, we show that $\alpha ({\mathcal{B}}_n)\le O(n!/1.97^n)$ improving on the previous known bound of $\alpha ({\mathcal{B}}_n)\le O(n!/{\sqrt{2}}^n)$ by [Kane-Lovett-Rao, FOCS 2017]. Our approach combines a higher-order version of their representation theoretic techniques with linear programming. With an explicit construction, we also improve their lower bound on $\alpha ({\mathcal{B}}_n)$ by a factor of $n/2$. This construction is based on a proper coloring of ${\mathcal{B}}_n$, which also gives an upper bound on the chromatic number $\chi ({\mathcal{B}}_n)$ of ${\mathcal{B}}_n$. Via known connections, the upper bound on $\alpha ({\mathcal{B}}_n)$ implies alphabet size lower bounds for a family of maximally recoverable codes on grid-like topologies.

34 pages, 4 figures, 1 table. (The only changes in version 2 are adding grant information.)