Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

• 成果类型: Article
• 署名作者: Huang, Hao
• 刊物名称: ANNALS OF MATHEMATICS
• ISSN/ISSBN: 0003-486X
• DOI: 10.4007/annals.2019.190.3.6
• 发表日期: 2019
• 页码: 949-955
• 关键词: block sensitivity

摘要

In this paper, we show that every (2(n-)(1) + 1)-vertex induced subgraph of the n-dimensional cube graph has maximum degree at least root n. This is the best possible result, and it improves a logarithmic lower bound shown by Chung, Furedi, Graham and Seymour in 1988. As a direct consequence, we prove that the sensitivity and degree of a boolean function are polynomially related, solving an outstanding foundational problem in theoretical computer science, the Sensitivity Conjecture of Nisan and Szegedy.