Tighter bounds on the independence number of the Birkhoff graph

DOI10.1016/J.EJC.2022.103564zbMATH Open1495.05216arXiv2007.05841OpenAlexW3041251342MaRDI QIDQ2145765FDOQ2145765

Leonardo Nagami Coregliano, Fernando Granha Jeronimo

Publication date: 20 June 2022

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

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.

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)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Four questions on Birkhoff polytopes
• The asymptotic volume of the Birkhoff polytope
• A Remark on Stirling's Formula
• Explicit Maximally Recoverable Codes With Locality
• The Independence Number of the Birkhoff Polytope Graph, and Applications to Maximally Recoverable Codes

Cited In (3)

• Complexes of graphs with bounded independence number
• Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques
• Improved covering results for conjugacy classes of symmetric groups via hypercontractivity

   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 👍 👎
• Title not available (Why is that?) 👍 👎
• Efficient dominating sets in Cayley graphs. 👍 👎
• Codes from incidence matrices of graphs 👍 👎

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)