Sensitivity conjecture proved!

Windows On Theory 2019-08-20

In a recent breakthrough, Hao Huang gave a 6 page paper proving the longstanding sensitivity conjecture. (Hat tip, Scott Aaronson and Gil Kalai. See this stackexchange post and this paper of Avishai for some links to the literature on this.)

The proof is beautiful and simple. I will write a few words here, but it is probably easier for you to just read the paper. The sensitivity conjecture was known to follow from the following statement: let $G_n$ be the Boolean Cube which is the degree $n$ graph on $N=2^n$ vertices identified with $\{0,1\}^n$ such that for every $x,y\in \{0,1\}^n$ , $x \sim y$ if their Hamming distance is one. Then, the maximum degree of every subgraph $H$ of $G_n$ of size $>N/2$ is at least $\sqrt{n}$ .

Hao proves the above statement by showing that there is a signing of the $N\times N$ adjacency matrix of $G_n$ that turns it into a matrix with $N/2$ eigenvalues equaling $+\sqrt{n}$ and $N/2$ eigenvalues equaling $-\sqrt{n}$ . That is, he shows (using a simple but clever inductive argument, see the 5 line proof of his Lemma 2.2) that there is an $N\times N$ matrix $A$ with entries in $\{ 0, \pm 1 \}$ whose nonzero entries correspond to the edges of the Boolean cube, and such that all the $N$ eigenvalues of $A$ are $\pm \sqrt{n}$ and they sum up to zero. (Note that this makes sense since $A$ should have the same Frobenius norm as the adjacency matrix of $G_n$ . The Frobenius norm squared is both the sum of squares of entries, which is $N\cdot n$ for $G_n$ which is a degree $n$ graph, and also equal to the sum of squares of the eigenvalues, which is $N\cdot n$ if all eigenvalues are $\pm \sqrt{n}$ .)

Once you have such a signing, the result follows from Cauchy’s Interlace Theorem that says that for every $N\times N$ matrix $A$ and any $M\times M$ matrix $B$ that is a principle sub-matrix of $A$ ,

$\lambda_{1+N-M}(A) \leq \lambda_1(B) \leq \lambda_1(A)$

where $\lambda_1(A) \geq \lambda_2(A) \cdots \geq \lambda_N(A)$ are the eigenvalues of $A$ and $\lambda_1(B)$ is the maximum eigenvalue of $B$ . A corollary of this (which is the only fact we need) is that if $A$ has its top eigenvalue $\lambda_1(A)$ with multiplicity $K$ (i.e., $\lambda_1(A)=\lambda_K(A)$ ), then every principle sub-matrix $B$ of order larger than $N-K$ will satisfy $\lambda_1(B) = \lambda_1(A)$ . (In fact, we only need $\lambda_1(B) \geq \lambda_1(A)$ .)

Indeed, suppose that $H$ is a subgraph of the Boolean cube of size $M>N/2$ . Then the principle submatrix $B$ of $A$ corresponding to the vertices of $H$ satisfies $\lambda_1(B) \geq \lambda_{1+N-M}(A) = \sqrt{n}$ (since $M>N/2$ and the first $N/2$ eigenvalues of $A$ are $+\sqrt{n}$ ).But it’s easy to show that for every matrix $B$ the maximum eigenvalue of $B$ is upper bounded by the maximum $\ell_1$ norm of its rows, which in our case is the maximum degree of the graph $H$ .