Tighter bounds on the independence number of the Birkhoff graph

DOI10.1016/J.EJC.2022.103564MaRDI QIDQ2145765zbMATH OpenOpenAlexFDO

Authors Leonardo Nagami Coregliano, Fernando Granha Jeronimo

Publication date 20 June 2022

Published in European Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2007.05841

zbMATH Keywords

linear programmingchromatic numberrepresentation theoryindependence numberBirkhoff graph

Mathematics Subject Classification ID

Linear programming (90C05) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

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)leO(n!/1.97^n)$ improving on the previous known bound of $alpha(mathcal{B}_n)leO(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.

Recommendations

• The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes
• Vertex reconstruction in Cayley graphs
• Graph theoretic methods in coding theory
• Bichromaticity of bipartite graphs
• Bicliques and eigenvalues
• Constructing codes identifying sets of vertices
• Topological bounds for graph representations over any field
• scientific article; zbMATH DE number 1803166
• Efficient dominating sets in Cayley graphs.
• Codes from incidence matrices of graphs

Cites work

• scientific article; zbMATH DE number 51129 (Why is no real title available?)
• scientific article; zbMATH DE number 1860211 (Why is no real title available?)
• scientific article; zbMATH DE number 848091 (Why is no real title available?)
• A Remark on Stirling's Formula
• Explicit Maximally Recoverable Codes With Locality
• Four questions on Birkhoff polytopes
• The asymptotic volume of the Birkhoff polytope
• The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes

Cited in

(4)

• Complexes of graphs with bounded independence number
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• The independence number of the Birkhoff polytope graph, and applications to maximally recoverable codes
• Improved covering results for conjugacy classes of symmetric groups via hypercontractivity

This page was built for publication: Tighter bounds on the independence number of the Birkhoff graph

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2145765)