Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs" [arXiv:2003.13166]

Gabriel Verret

Published 2020-04-03Version 1

Recently, Huang [arXiv:1907.00847] gave a very elegant proof of the Sensitivity Conjecture by proving that hypercube graphs have the following property: every induced subgraph on a set of more than half the vertices has maximum degree at least $\sqrt{d}$, where $d$ is the valency of the hypercube. This was generalised by Alon and Zheng [arXiv:2003.04926] who proved that every Cayley graph on an elementary abelian $2$-group has the same property. Very recently, Potechin and Tsang [arXiv:2003.13166] proved an analogous results for Cayley graphs on abelian groups. They also conjectured that all Cayley graphs have the analogous property. We give an infinite family of counterexamples to this conjecture.