On sensitivity in bipartite Cayley graphs
On sensitivity in bipartite Cayley graphs
复制标题
关于二分凯莱图的敏感性
DOI：
10.1016/j.jctb.2022.01.002
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
K. Knauer
中科院分区：
文献类型：
--
作者：
Ignacio Garc'ia;K. Knauer
Huang证明了d维超立方体Qd的每一个超过一半顶点的集合都诱导出一个最大度至少为d的子图，这是紧的，这是Chung，Füredi，Graham和Seymour的一个结果。黄问是否可以获得类似的结果，其他高度对称的图形。首先，我们提出了三个无限家族的Cayley图的无界度，其中包含诱导子图的最大度为1的一半以上的顶点。特别是，这驳斥了一个猜想的Potechin和曾，其中第一个反例显示最近由莱纳和Verret。第一个家庭包括dihedrants和包含一个零星的反例遇到了Lehner和Verret。第二类是对称群的边传递的星星图。第三个族的所有成员都是d-正则的，包含一个在d 2 d− 1-分数的顶点上的诱导匹配。这是最大可能的，并回答了Lehner和Verret的问题。其次，我们考虑黄的下界与子立方体的图，并表明相应的下界是紧的产品的Coxeter群的类型An，I2（2 k+ 1），和最例外的情况下。我们认为，Coxeter群是一个合适的推广的超立方体相对于黄的问题。最后，我们证明了射影平面的Levi图和Lubotzky，菲利普斯和Sarnak的Ramanujan图的一半以上顶点上的诱导子图具有无界度.这给出了类凯莱图的性质类似的黄的结果。然而，与Coxeter群相反，这些图没有子立方体。
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 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 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 A n, I 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.