论文标题
关于两分的cayley图中的灵敏度
On sensitivity in bipartite Cayley graphs
论文作者
论文摘要
黄证明，每组超过一半的顶点是$ d $ d $二维的hypercube $ q_d $，诱导了最高度的最高学位，至少$ \ sqrt {d} $，这是由于Chung，füredi，füredi，graham，graham和seymour的结果。黄问是否可以为其他高度对称图获得类似的结果。 首先，我们介绍了三个无限程度的Cayley图的家族，其中包含一半以上顶点的最高学位$ 1 $的诱导子图。特别是，这反驳了Potechin和Tsang的猜想，Lehner和Verret最近为此展示了第一个反样本。第一个家庭由Dihedrants组成，并包含Lehner和Verret早些时候遇到的零星反例。第二个家庭是恒星图，这些是对称组的边缘传输cayley图。第三家族的所有成员都是$ d $ - regular，其中包含$ \ frac {d} {2d-1} $ - 顶点分数的诱导匹配。这是最大的，并回答了雷纳和Verret的问题。 其次，我们考虑了带有子立管的图形的Huang的下限，并表明相应的下限对于$ \ Mathbf {a_n} $，$ \ mathbf {i_2}（2k+1）$的Coxeter组的产品紧密。我们认为，相对于黄的问题，Coxeter群是对超立方体的合适概括。 最后，我们表明，在Levi图和Lubotzky，Phillips和Sarnak的Ramanujan图的一半以上的诱导子图上具有无限程度。这提供了类似于黄的结果所提供的属性的Cayley图。但是，与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 $\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}{2d-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_n}$, $\mathbf{I_2}(2k+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.
