MathSciDoc: An Archive for Mathematician ∫

 
Log In
Sign Up
Help
Go
 

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

Hao Huang Emory University

Combinatorics Information Theory mathscidoc:2005.06001

Best Paper Award in Applied Mathematics in 2020

Annals of Mathematics, 190, 949-955, 2019.11
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.
No keywords uploaded!
[ Download ] [ 2020-05-12 02:46:47 uploaded by richardhh ] [ 1001 downloads ] [ 0 comments ] 
@inproceedings{hao2019induced,
  title={Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture},
  author={Hao Huang},
  url={http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20200512024647968550671},
  booktitle={Annals of Mathematics},
  volume={190},
  pages={949-955},
  year={2019},
}
Hao Huang. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. 2019. Vol. 190. In Annals of Mathematics. pp.949-955. http://archive.ymsc.tsinghua.edu.cn/pacm_paperurl/20200512024647968550671.
Please log in for comment!
 
 
Contact us: office-iccm@tsinghua.edu.cn | Copyright Reserved