敏感性猜想与有符号超立方体

《ACM Transactions on Computation Theory》：Sensitivity conjecture and signed hypercubes

利用谱技术和线性依赖性分析，证明高维超立方体H?任意超过半数顶点的子图最大度数至少为√n，完成敏感度猜想证明。改进结果发现此类子图中存在奇偶顶点各至少n个距离≤2的邻居，并关联Erd?s问题与Ambainis函数，建立挫折指数上下界。

　　

摘要总结

要查看此由人工智能生成的摘要，您必须具有高级访问权限。

了解更多登录

摘要

摘要

利用光谱技术，H. Huang 证明了在维度为 n 的超立方体 H_n 的每个子图中，如果该子图包含超过一半的顶点，那么其最大度至少为 $\sqrt{n}$。结合之前的研究，这完成了对敏感性猜想的证明。在这项工作中，我们展示了如何利用与超立方体顶点相关的向量的线性依赖性和独立性来推导 Huang 的结果。我们的方法对 Huang 的结果进行了几项改进。特别是，我们证明了在 H_n 的任何包含超过一半顶点的子图中，都存在两个顶点：一个为奇数奇偶性，另一个为偶数奇偶性，每个顶点都与至少 n 个顶点的距离不超过 2。作为一个应用实例，我们展示了对于任何布尔函数 f，其多项式度数上限为 $s_0\left(f\right)s_1\left(f\right)$，这一结论蕴含了敏感性猜想（但敏感性猜想本身并不直接推出这一结论）。利用这些线性依赖性，我们揭示了在距离不超过 3 的子图中的邻居节点之间的结构关系。

Huang 证明中的一个关键步骤是为 H_n 的边分配符号（+，?），使得每个 4-循环上的符号乘积为 ?。将负边的集合称为“签名”，可以观察到在 H_n 中总共有 $2^{2^n?1}$ 个满足此条件的签名，且任意两个这样的签名的对称差是一个边割。因此，一个非常有趣的问题是找到所有这些签名中最小的一个。这在有符号图的研究中被称为“挫折指数”。在这里，我们为这个参数提供了下界和上界，并观察到当 n 是 4 的幂时，这两个界限是一致的。然后我们建立了与其他研究的紧密联系：一方面与 Erd?s 关于超立方体中最大无 4-循环子图的边数问题有关；另一方面与 Ambainis 函数有关，这些函数用于展示度数与查询复杂度的下界之间的关系。

总结

要查看此由人工智能生成的通俗语言摘要，您必须具有高级访问权限。