Processing math: 0%
\def\<#1>{\left<#1\right>}
\newcommand{\R}{\mathcal{R}}
\renewcommand{\deg}[2]{\mathrm{deg}_{#2}(#1)}
\newcommand{\kw}[1]{\mathfrak{c}(#1)}
Sensitivity conjecture (Problem 14.16) solved
Let, as in the book, Q_n be the graph whose vertices are vectors in \{0,1\}^n, and two vectors are adjacent if they differ in exactly one coordinate.
Theorem (Huang [1]):
Every induced subgraph of Q_n with more than 2^{n-1} vertices has a vertex of degree at least \sqrt{n}.
By the Gostman-Linial result (Thm. 14.18), this implies the inequality
s(f)\geq \sqrt{\mbox{deg}(f)} for every Boolean function f, where s(f) is the sensitivity of f, and \mbox{deg}(f) is the degree of f [the minimum degree of a multilinear real polynomial p that takes the same values as f on all binary vectors].
The proof in [1] is amazingly simple! See also its one-page version by Knuth [2] or a survey paper [3] or search for "sensitivity" on ECCC for subsequent papers. Or just visit the author's home page for links to blogs on which this result was discussed.
References:
- [1] H. Huang, Induced subgraphs of hypercubes and
a proof of the Sensitivity Conjecture, Annals of Mathematics 190 (2019), 949-955. Preprint in arxiv.
- [2] D. Knuth, A computational proof of Huang's degree theorem, local copy
- [3] R. Karthikeyan, S. Sinha, V. Patil, On the resolution of the sensitivity conjecture, Bulletin of AMS, 57 (2020), 615-638 DOI
S. Jukna, 27.04.2020