Very recently, Hao Huang proved the Sensitivity Conjecture, which had been open for 30 years or so. Here is Huang's preprint, a discussion on Scott Aaronson's blog, and a one-page streamlined proof by Don Knuth.

Huang's proof relies on the existence of an edge weighing $w$ on the hypercube graph $Q_n$. Where if one forms the $2^n\times2^n$ matrix $U_n$ ($= A_n/\sqrt n$ from Huang's paper) where the $(i,j)$-th entry of $U_n$ is $w(v_i,v_j)$ for some enumeration $v_1,\ldots,v_{2^n}$ of the vertices of $Q_n$, then $U_n$ is both unitary and Hermitian. (Huang's matrix is actually symmetric but the more general Hermitian case also covers the Klee-Minty matrix described by Knuth in a footnote.)

It's easy to see that Huang's result holds for any graph $G=(V,E)$ with a weighting $w$ as described above:

Theorem. Suppose there is a weighting $w$ of the edges of the graph $G$ such that the matrix $U$ is both Hermitian and unitary, where the $(i,j)$-th entry of $U$ is $w(v_i,v_j)$ for some enumeration $v_1,v_2,\ldots,v_n$ of $V_G$. Then for every set $H \subseteq V$ with $|H| > n/2$, there is a $v \in H$ which is connected to at least $1/\Vert U\Vert_{\infty}$ vertices inside $H$, where $\|U\|_\infty$ is the maximum absolute value $|w(u,v)|$ ranging over edges $uv$ of $G$.

(In the case of Huang's proof, $U = \frac{1}{\sqrt{n}}A_n$ has all entries in $\{0,\pm1/\sqrt{n}\}$ and the result follows immediately. In the Klee-Minty case the entries of $U = \frac{i}{\sqrt n}\widehat{A}_n$ are all in $\{0,\pm i/\sqrt{n}\},$ using notation from Knuth.)

It is surprising that this was not noticed for 30 years until Huang put the pieces together. (The Klee-Minty cube has been around since 1973!) Why this was never noticed is interesting but, even after this fact, there are still some follow-up questions:

• Which graphs have Hermitian unitary edge weights as above?

• Is there an algorithm to build such edge weights, given that one exists?

• How hard is it to compute the minimum value of $\Vert U \Vert_\infty,$ given that such a weighting exists?

And probably many more related questions... Since there is strong evidence that connections between existing literature are missing, this is an opportune time to fix these lacunas.