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

Huang (2019, Introduction) studies the $n$-dimensional hypercube graph $Q_n$, whose $2^n$ vertices are the binary strings in $\{0,1\}^n$ and whose edges join strings differing in exactly one coordinate. In 1988, Chung, Furedi, Graham and Seymour proved that every induced subgraph on more than half the vertices of $Q_n$ has maximum degree at least $(1/2-o(1))\log_2 n$, and they constructed an induced subgraph on exactly $2^{n-1}+1$ vertices whose maximum degree is only $\lceil\sqrt n\rceil$. Huang's paper closes the gap between these two bounds completely: Theorem 1.1 states that every induced subgraph $H$ of $Q_n$ on at least $2^{n-1}+1$ vertices satisfies $\Delta(H) \ge \sqrt{n}$, matching the earlier construction exactly.