Document type
ArticleVersion
Published versionPublication date
Publication license
Please use this identifier to cite or link to this item: https://hdl.handle.net/2445/208007
On sensitivity in bipartite Cayley graphs
Journal Title
Authors
Director/Tutor
Additional contribution
Journal ISSN
Volume Title
Abstract
Huang proved that every set of more than half the vertices of the $d$-dimensional hypercube $Q_d$ induces a subgraph of maximum degree at least $\sqrt{d}$, which is tight by a result of Chung, Füredi, Graham, and Seymour. Huang asked whether similar results can be obtained for other highly symmetric graphs. First, we present three infinite families of Cayley graphs of unbounded degree that contain induced subgraphs of maximum degree 1 on more than half the vertices. In particular, this refutes a conjecture of Potechin and Tsang, for which first counterexamples were shown recently by Lehner and Verret. The first family consists of dihedrants and contains a sporadic counterexample encountered earlier by Lehner and Verret. The second family are star graphs, these are edge-transitive Cayley graphs of the symmetric group. All members of the third family are $d$-regular containing an induced matching on a $\frac{d}{2 d-1}$-fraction of the vertices. This is largest possible and answers a question of Lehner and Verret. Second, we consider Huang's lower bound for graphs with subcubes and show that the corresponding lower bound is tight for products of Coxeter groups of type $\mathbf{A}_{\mathbf{n}}, \mathbf{I}_{\mathbf{2}}(2 k+1)$, and most exceptional cases. We believe that Coxeter groups are a suitable generalization of the hypercube with respect to Huang's question. Finally, we show that induced subgraphs on more than half the vertices of Levi graphs of projective planes and of the Ramanujan graphs of Lubotzky, Phillips, and Sarnak have unbounded degree. This gives classes of Cayley graphs with properties similar to the ones provided by Huang’s results. However, in contrast to Coxeter groups these graphs have no subcubes.
Related resource
Subject (English)
Citation
Citation
GARCÍA MARCO, Ignacio and KNAUER, Kolja. On sensitivity in bipartite Cayley graphs. Journal of Combinatorial Theory Series B. 2022. Vol. 154, num. May 2022, pags. 211-238. ISSN 0095-8956. [consulted: 8 of October of 2026]. Available at: https://hdl.handle.net/2445/208007