Very recently, Hao Huang proved the Sensitivity Conjecture, which had been open for 30 years or so. Here is [Huang's preprint](http://www.mathcs.emory.edu/~hhuan30/papers/sensitivity_1.pdf), a [discussion on Scott Aaronson's blog](https://www.scottaaronson.com/blog/?p=4229), and a one-page streamlined [proof by Don Knuth](https://www.cs.stanford.edu/~knuth/papers/huang.pdf).

Huang's proof relies on the existence of an edge weighing $w$ on the [hypercube graph](https://en.wikipedia.org/wiki/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 \notin 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](https://en.wikipedia.org/wiki/Klee%E2%80%93Minty_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.