Worked solution: Huang's signed hypercube adjacency matrix proof of the sensitivity conjecture (2019)

The reformulation rests on two classical facts about the hypercube graph $Q_n$, whose $2^n$ vertices are the binary strings of $\{0,1\}^n$ joined when they differ in one coordinate. For a Boolean function $f$, sensitivity at input $x$ counts neighbours of $x$ in $Q_n$ where $f$ flips value, so $s(f)$ is exactly the maximum degree of the bipartite subgraph induced between the level sets $f^{-1}(0)$ and $f^{-1}(1)$. Nisan and Szegedy (1992) proved $s(f)$ and $\deg(f)$ are polynomially related to every other standard complexity measure (decision-tree depth, certificate complexity, block sensitivity $bs(f)$) except each other, and conjectured $\deg(f) \le s(f)^C$ for some constant $C$.

The graph-theoretic equivalent was already quantified: Chung, Füredi, Graham and Seymour (1988) proved every induced subgraph $H$ of $Q_n$ on at least $2^{n-1}+1$ vertices has $\Delta(H) \ge (\tfrac12 - o(1))\log_2 n$, and built an induced subgraph on exactly $2^{n-1}+1$ vertices with $\Delta(H) = \lceil\sqrt{n}\rceil$ by taking a ball around the all-zero word. Closing a $\sqrt{n}$-versus-$\log n$ gap of thirty years' standing, Huang's Theorem 1.1 asserts the displayed bound $\Delta(H) \ge \sqrt{n}$, matching that construction exactly and therefore the best possible constant.

Because the statement only asks about maximum degree, one might expect a purely combinatorial proof; the surprise is that the optimal bound comes from linear algebra on a cleverly signed adjacency matrix, assembled in the next four steps.