%0 Journal Article %1 huang2019induced %A Huang, Hao %D 2019 %K mathematics proof-systems theory %T Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture %U http://arxiv.org/abs/1907.00847 %X 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 $n$. This result is best possible, and improves a logarithmic lower bound shown by Chung, Füredi, 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.

@article{huang2019induced, abstract = {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 $\sqrt{n}$. This result is best possible, and improves a logarithmic lower bound shown by Chung, F\"uredi, 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.}, added-at = {2019-09-13T18:46:26.000+0200}, author = {Huang, Hao}, biburl = {https://www.bibsonomy.org/bibtex/25793348add84634c903ec350c5d7a403/kirk86}, description = {[1907.00847] Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture}, interhash = {192b43ed1c84fb467c233af4c0c188c4}, intrahash = {5793348add84634c903ec350c5d7a403}, keywords = {mathematics proof-systems theory}, note = {cite arxiv:1907.00847}, timestamp = {2019-09-13T18:46:26.000+0200}, title = {Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture}, url = {http://arxiv.org/abs/1907.00847}, year = 2019 }