Voir la notice de l'article provenant de la source Annals of Mathematics website
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 is the best possible result, and it 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{10_4007_annals_2019_190_3_6,
author = {Hao Huang},
title = {Induced subgraphs of hypercubes and a proof of the {Sensitivity} {Conjecture}},
journal = {Annals of mathematics},
pages = {949--955},
publisher = {mathdoc},
volume = {190},
number = {3},
year = {2019},
doi = {10.4007/annals.2019.190.3.6},
mrnumber = {4024566},
zbl = {07128144},
language = {en},
url = {http://geodesic.mathdoc.fr/articles/10.4007/annals.2019.190.3.6/}
}
TY - JOUR AU - Hao Huang TI - Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture JO - Annals of mathematics PY - 2019 SP - 949 EP - 955 VL - 190 IS - 3 PB - mathdoc UR - http://geodesic.mathdoc.fr/articles/10.4007/annals.2019.190.3.6/ DO - 10.4007/annals.2019.190.3.6 LA - en ID - 10_4007_annals_2019_190_3_6 ER -
%0 Journal Article %A Hao Huang %T Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture %J Annals of mathematics %D 2019 %P 949-955 %V 190 %N 3 %I mathdoc %U http://geodesic.mathdoc.fr/articles/10.4007/annals.2019.190.3.6/ %R 10.4007/annals.2019.190.3.6 %G en %F 10_4007_annals_2019_190_3_6
Hao Huang. Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture. Annals of mathematics, Tome 190 (2019) no. 3, pp. 949-955. doi: 10.4007/annals.2019.190.3.6
Cité par Sources :