Tighter Bounds on the Independence Number of the Birkhoff Graph
share
The Birkhoff graph ℬ_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 α(ℬ_n) of ℬ_n, namely, we show that α(ℬ_n) ≤ O(n!/1.97^n) improving on the previous known bound of α(ℬ_n) ≤ O(n!/√(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 α(ℬ_n) by a factor of n/2. This construction is based on a proper coloring of ℬ_n, which also gives an upper bound on the chromatic number χ(ℬ_n) of ℬ_n. Via known connections, the upper bound on α(ℬ_n) implies alphabet size lower bounds for a family of maximally recoverable codes on grid-like topologies.
READ FULL TEXT