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