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

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

该研究利用谱技术证明超立方体Hn的每个超过半数顶点诱导的子图最大度至少为n，结合前人工作完成敏感度猜想证明，并通过线性依赖性方法改进结果，建立布尔函数多项式次数上界与Erd?s问题和Ambainis函数的联系。

　　

摘要AI摘要

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

了解更多登录

摘要

摘要

利用谱技术，H. Huang证明了在维度为n的超立方体H_n中，如果一个子图包含超过一半的顶点，那么该子图的最大度至少为$\sqrt{n}$。结合之前的研究，这完成了对敏感性猜想的证明。在这项工作中，我们展示了如何利用与超立方体顶点相关的向量的线性依赖性和独立性来推导Huang的结果。我们的方法对Huang的结果进行了几项改进。特别是，我们证明了在H_n的任何包含超过一半顶点的子图中，存在两个顶点：一个为奇数奇偶性，另一个为偶数奇偶性，每个顶点与最多2个其他顶点的距离都至少为n。作为一个应用实例，我们证明了对于任何布尔函数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函数有关，这些函数用于证明度数与查询复杂度的下界之间的区别。

AI摘要

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