#subgraphs

超立方体的导出子图与灵敏度猜想的证明
Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture(arxiv.org)
2020-9-2 2:45
下载PDF摘要：本文证明了$n$维立方图的每个$(2^{n-1}+1)$-点诱导子图的最大度至少为$\sqrt{n}$。这个结果是最好的，改进了Chung，Füredi，Graham和Seymour在1988年所证明的对数下界。作为直接推论，我们证明了布尔函数的灵敏度和次数是多项式相关的，从而解决了理论计算机科学中的......