Tighter bounds on the independence number of the Birkhoff graph (Q2145765)

The Birkhoff graph \(\mathcal{B}_{n}\) is the Cayley graph of the symmetric group \(\mathcal{S}_{n}\), where two permutations are adjacent if they differ by a single cycle. Using techniques from representation theory, \textit{D. Kane} et al. [SIAM J. Comput. 48, No. 4, 1425--1435 (2019; Zbl 1419.05217)] obtained the following upper bound on the independence number \(\alpha(\mathcal{B}_{n})\) of \(\mathcal{B}_{n}\): \(\alpha(\mathcal{B}_{n}) \leq \frac{n!}{\sqrt2^{n-4}}\) for all \(n \in \mathbb{N}_{+}\). In this paper, the authors combine a higher-order version of KLR's representation theoretic techniques with linear programming to obtain \(\alpha(\mathcal{B}_{n}) \leq O(\frac{n!}{1.97^{n}})\), which also improves the lower bound on the size of the alphabet of a maximally recoverable code in the \(T_{(1,1,1)}\) topology of [\textit{P. Gopalan} et al., in: Proceedings of the 28th annual ACM-SIAM symposium on discrete algorithms, SODA 2017, Barcelona, Spain, January 16--19, 2017. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 2092--2108 (2017; Zbl 1409.68092)] from \(\Omega(\sqrt2^{n})\) to \(\Omega(1.97^{n})\). With an explicit construction, the authors also improve KLR's lower bound by a factor of \(n/2\), a construction which is based on a new proper coloring of \(\mathcal{B}_{n}\), which provides an upper bound on the chromatic number \(\chi(\mathcal{B}_{n})\) of \(\mathcal{B}_{n}\).