.png){kind=icon}
返回
Sensitivity Conjecture and Signed Hypercubes
.png){kind=icon}
PRE
AI
DOI：10.1145/3777401.png)
.png){kind=icon}
原文求助.png){kind=icon}
分享.png){kind=icon}
收藏
摘要
En 中文
利用光谱技术，黄辉证明了超立方体Hn的每个在超过半数顶点上诱导的子图的最大度至少为根号n。结合先前的工作，这完成了敏感度猜想的证明。在本工作中，我们展示了如何利用与超立方体顶点相关联的向量的线性依赖和独立性来推导黄辉的结果。我们的方法对黄辉的结果进行了多项改进。特别是，我们证明了在任何在Hn中超过半数顶点诱导的子图中，存在两个顶点，一个为奇偶性，另一个为偶偶性，每个顶点至少有n个距离不超过2的顶点。作为应用，我们证明对于任何布尔函数f，f的多项式度数被s0(f) s1(f)上限所限制，这一陈述意味着敏感度猜想（但并非直接由敏感度猜想所暗示）。利用这些线性依赖关系，我们展示了距离不超过三的诱导子图中邻域的结构关系。黄辉证明中的关键步骤是为Hn的边分配符号（+，-），使得每个4-环上的符号乘积为负。被称为签名的负边集合满足这一条件，可以观察到在Hn上有总共22n-1个这样的签名，并且任意两个此类签名的对称差是一个边割。一个有趣的问题是找出所有这些签名中最小的尺寸。这被称为有符号图研究中的挫败指数。在这里，我们为该参数提供了下界和上界，观察到当n是4的幂时，这两个界相等。然后我们建立了与其他研究的强关联：一方面与Erdős关于超立方体中最大4-环自由子图的边数问题相关，另一方面与Ambainis函数相关，后者用于展示查询复杂度中度和对手下界之间的分离。
Keyword:
Boolean function
sensitivity
signed graphs
frustration index
