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