Geodesic
Counterexamples to “A conjecture on induced subgraphs of Cayley graphs”
Ars Mathematica Contemporanea, Tome 19 (2020) no. 1, pp. 77-82.

Voir la notice de l'article provenant de la source Ars Mathematica Contemporanea website

Recently, Huang 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 √d, where d is the valency of the hypercube. This was generalised by Alon and Zheng who proved that every Cayley graph on an elementary abelian 2-group has the same property. Very recently, Potechin and Tsang proved an analogous results for Cayley graphs on abelian groups. They also conjectured that all Cayley graphs have the analogous property. We disprove this conjecture by constructing various counterexamples, including an infinite family of Cayley graphs of unbounded valency which admit an induced subgraph of maximum valency 1 on a set of more than half the vertices.
DOI : 10.26493/1855-3974.2301.63f
Keywords: Cayley graphs, vertex-transitive graphs, sensitivity conjecture 
@article{10_26493_1855_3974_2301_63f,
     author = {Florian Lehner and Gabriel Verret},
     title = {Counterexamples to {{\textquotedblleft}A} conjecture on induced subgraphs of {Cayley} graphs{\textquotedblright}},
     journal = {Ars Mathematica Contemporanea},
     pages = {77--82},
     publisher = {mathdoc},
     volume = {19},
     number = {1},
     year = {2020},
     doi = {10.26493/1855-3974.2301.63f},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2301.63f/}
}
TY  - JOUR
AU  - Florian Lehner
AU  - Gabriel Verret
TI  - Counterexamples to “A conjecture on induced subgraphs of Cayley graphs”
JO  - Ars Mathematica Contemporanea
PY  - 2020
SP  - 77
EP  - 82
VL  - 19
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2301.63f/
DO  - 10.26493/1855-3974.2301.63f
LA  - en
ID  - 10_26493_1855_3974_2301_63f
ER  - 
%0 Journal Article
%A Florian Lehner
%A Gabriel Verret
%T Counterexamples to “A conjecture on induced subgraphs of Cayley graphs”
%J Ars Mathematica Contemporanea
%D 2020
%P 77-82
%V 19
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2301.63f/
%R 10.26493/1855-3974.2301.63f
%G en
%F 10_26493_1855_3974_2301_63f
Florian Lehner; Gabriel Verret. Counterexamples to “A conjecture on induced subgraphs of Cayley graphs”. Ars Mathematica Contemporanea, Tome 19 (2020) no. 1, pp. 77-82. doi : 10.26493/1855-3974.2301.63f. http://geodesic.mathdoc.fr/articles/10.26493/1855-3974.2301.63f/

Cité par Sources :