论文标题
在Cayley图的诱导子图上的猜想
A Conjecture on Induced Subgraphs of Cayley Graphs
论文作者
论文摘要
在本文中，我们提出了以下猜想，该猜想概括了Huang [Hua19]在他最近的敏感性猜想的突破性证明中证明的一个定理。我们推测，对于任何Cayley图，$ g $上的任何Cayley图$ x =γ（g，s）$，如果$ u \ u \ u \ subseteq g $具有尺寸$ | u | > | g |/2 $，然后$ u $上的$ x $的诱导子图具有最高学位至少$ \ sqrt {| s |/2} $。使用最近的Alon和Zheng [AZ20]的想法，他们在$ g = z_2^n $时证明了这种猜想，我们证明，每当$ g $是Abelian时，这个猜想都是正确的。我们还观察到，要为图形$ x $保留这个猜想，需要一些对称性：对于$ x $来说，仅是常规和两部分是不足的。
In this paper, we propose the following conjecture which generalizes a theorem proved by Huang [Hua19] in his recent breakthrough proof of the sensitivity conjecture. We conjecture that for any Cayley graph $X = Γ(G,S)$ on a group $G$ and any generating set $S$, if $U \subseteq G$ has size $|U| > |G|/2$, then the induced subgraph of $X$ on $U$ has maximum degree at least $\sqrt{|S|/2}$. Using a recent idea of Alon and Zheng [AZ20], who proved this conjecture for the special case when $G = Z_2^n$, we prove that this conjecture is true whenever $G$ is abelian. We also observe that for this conjecture to hold for a graph $X$, some symmetry is required: it is insufficient for $X$ to just be regular and bipartite.
