超立方体的导出子图与灵敏度猜想的证明

2020-09-02 02:45:25

下载PDF摘要:本文证明了$n$维立方图的每个$(2^{n-1}+1)$-点诱导子图的最大度至少为$\sqrt{n}$。这个结果是最好的,改进了Chung,Füredi,Graham和Seymour在1988年所证明的对数下界。作为直接推论,我们证明了布尔函数的灵敏度和次数是多项式相关的,从而解决了理论计算机科学中的一个突出的基本问题,即Nisan和Szegedy的灵敏度猜想。