论文标题
Birkhoff图的独立性数量更紧密
Tighter Bounds on the Independence Number of the Birkhoff Graph
论文作者
论文摘要
Birkhoff图$ \ Mathcal {B} _n $是对称组$ s_n $的Cayley图，如果单个周期有两个排列，则两个排列相邻。我们的主要结果是$ \ Mathcal {b} _n $的独立数$α（\ Mathcal {b} _n）$更紧密的上限，也就是说，我们表明$α（\ nathcal {b} _n） \ le o（n！/\ sqrt {2}^{n}）$ [kane-lovett-rao，focs 2017]。我们的方法将其表示理论技术的高阶版本与线性编程结合在一起。通过明确的结构，我们还将其下限提高了$α（\ Mathcal {b} _n）$的下限，将其提高到$ n/2 $。该结构基于$ \ MATHCAL {B} _n $的适当着色，它也给出了$ \ MATHCAL {B} _n $的色度$χ（\ Mathcal {B} _n）$的上限。通过已知的连接，上的上限在$α（\ Mathcal {B} _n）$上的上限意味着在类似网格的拓扑结构的最大可回收代码家族的字母大小下限。
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 $α(\mathcal{B}_n)$ of $\mathcal{B}_n$, namely, we show that $α(\mathcal{B}_n) \le O(n!/1.97^n)$ improving on the previous known bound of $α(\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 $α(\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 $χ(\mathcal{B}_n)$ of $\mathcal{B}_n$. Via known connections, the upper bound on $α(\mathcal{B}_n)$ implies alphabet size lower bounds for a family of maximally recoverable codes on grid-like topologies.
