论文标题
对“ Cayley图的诱发子图的猜想”的反例[Arxiv：2003.13166]
Counterexamples to "A Conjecture on Induced Subgraphs of Cayley Graphs" [arXiv:2003.13166]
论文作者
论文摘要
最近，Huang通过证明HyperCube图具有以下属性，给出了敏感性猜想的非常优雅的证据：其一组超过一半的顶点上的每个引起的子图具有最大程度至少$ \ sqrt {d} $，其中$ d $是$ d $。这是由Alon和Zheng概括的，他们证明了小学Abelian $ 2 $ -Group上的每个Cayley图具有相同的属性。最近，Potechin和Tsang证明了Abelian群体的Cayley图的类似结果。他们还猜想所有Cayley图具有类似的属性。我们通过构建各种反例，包括无界价值的无限cayley图家族来反驳这一猜想，该家族在其一半以上的顶点中接受了最大价值$ 1 $的诱发子图。
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 its vertices has maximum degree at least $\sqrt{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 its vertices.
