Graphs with Hermitian Unitary Edge Weights

Question

Very recently, Hao Huang proved the Sensitivity Conjecture, which had been open for 30 years or so. Huang's proof is surprisingly short and easy. 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 a $2^n \times 2^n$ Hermitian unitary matrix $U_n$ ($= A_n/\sqrt n$, where $A_n$ is from Huang's paper) such that, for some enumeration $v_1,v_2,\ldots,v_{2^n}$ of the vertices of the hypercube graph $Q_n$, we have that the $(i,j)$th entry of $U_n$ is $0$ unless $(v_i,v_j)$ is an edge of $Q_n$. (Huang's matrix is actually symmetric but the more general Hermitian case also handles the skew-symmetric Klee-Minty matrix described by Knuth in a footnote.)

We can view this Hermitian unitary matrix as a (complex-valued) weighting on the edges of the graph. In the general case, for a graph $G = (V,E)$, lets say that a weighting $w:E \to \mathbb{C}$ is Hermitian unitary if the matrix $U$ whose entries are $$u_{ij} = \begin{cases} w(v_i,v_j) & \text{if $(v_i,v_j) \in E$,} \\ 0 & \text{otherwise,} \end{cases}$$ is Hermitian unitary for any (and hence all) enumerations $v_1,v_2,\ldots,v_n$ of $V$.

In other words:

• Hermitian: $w(u,v) = \overline{w(v,u)}$ for all $(u,v) \in E$
• Unitary: for all $u,v \in V$, $$\sum_{\substack{t \in V \\ (u,t),(v,t) \in E}} w(u,t)\overline{w(v,t)} = \sum_{\substack{t \in V \\ (u,t),(t,v) \in E}} w(u,t)w(t,v) = \begin{cases} 1 & \text{if $u = v$,} \\ 0 & \text{otherwise.} \end{cases}$$

Theorem. Suppose $G = (V,E)$ has a Hermitian unitary weighting $w$. 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 weightings as above? Is this rare, common, neither?

• 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 a Hermitian unitary 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 bridge these gaps.

---

Since the theorem above is somewhat more general than what Huang proved, here is a quick proof:

Since $U$ is Hermitian, it is unitarily diagonalizable with real eigenvalues. Since $U$ is unitary, the only possible eigenvalues are $\pm1.$ One of the two eigenspaces $E_{\pm} = \{ x : Ux = \pm x \}$ has dimension at least $n/2.$ Replacing $U$ by $-U$ if necessary, we may suppose $\dim E_{+} \geq n/2.$ Since $|V - H| < n/2,$ we can find an eigenvector $x \in E_{+}$ such that $x_i = 0$ when $v_i \notin H.$ Scaling $x$ if necessary, we may assume that $\|x\|_\infty = 1$ and that there is a $j$ with $x_j = 1.$ Then $$1 = |x_j| = \Big|\sum_{k=1}^n w(v_j,v_k)x_k\Big| \leq \sum_{k=1}^n |w(v_j,v_k)||x_k| \leq \Vert U\Vert_\infty |\{ k \mid w(v_j,v_k) \neq 0, x_k \neq 0\}|.$$ Now $v_j \in H$ since $x_j \neq 0$ and since $$\{ k \mid w(v_j,v_k) \neq 0, x_k \neq 0\} \subseteq \{ k \mid (v_j,v_k) \in E, v_k \in H \}$$ we see that $v_j$ is connected to at least $1/\Vert U \Vert_\infty$ vertices in $H.$

Answer 1

I can answer my first question for the class of bipartite graphs.

Theorem. A bipartite graph has a Hermitian unitary weighting if and only if it has a perfect matching.

Let $G = (V,E)$ be a bipartite graph and list the vertices as $v_1,v_2,\ldots,v_n$ so that $\{v_1,\ldots,v_m\}$ and $\{v_{m+1},\ldots,v_n\}$ is a bipartition of $G$ for some $m < n$. For any Hermitian weighting $w:E \to \mathbb C$ (not necessarily unitary) the associated matrix $U$ has the shape $$U=\begin{pmatrix} 0 & A^* \\ A & 0 \end{pmatrix}.$$ This matrix $U$ will be unitary precisely if $A^*A = I$ and $AA^* = I$, i.e., if $n=2m$ and $A$ is unitary (not necessarily Hermitian).

The if direction of the theorem is now clear: If $G$ has a perfect matching, then $n$ is even and we may list the vertices $v_1,v_2,\ldots,v_n$ in such a way that $\{v_1,\ldots,v_m\}$ and $\{v_{m+1},\ldots,v_n\}$ is a bipartition and $(v_1,v_{m+1}),(v_2,v_{m+2}),\ldots,(v_m,v_{2m})$ is a perfect matching. Then choosing $A = I$ gives a Hermitian unitary $U$. In other words, the weighting $w$ is the characteristic function of a perfect matching. $\square$

Note that the $U$ just constructed from a perfect matching has $\|U\|_\infty = 1$, so the theorem from the question doesn't have a strong conclusion, but this is the optimal conclusion when $G$ is a perfect matching.

For the only if direction: suppose that we have a Hermitian unitary weighting $w$ and that we decomposed the associated Hermitian unitary matrix as described above. So $n = 2m$ and the matrix $A$ is unitary. To see that $G$ has a perfect matching, it suffices to check the Hall condition. For any $J \subseteq \{1,\ldots,m\}$, the set $K = \{ k \mid \exists j \in J,(v_j,v_{m+k}) \in E\}$ has size at least $|J|$. To see this, let $a_1,a_2,\ldots,a_m$ list the rows of $A.$ These row vectors $a_j$ with $j \in J$ live in the subspace $\{ x \in {\mathbb C}^m : \forall i, x_i \neq 0 \to i \in K \}.$ This is a subspace of dimension $|K|$. Since the rows of $A$ are linearly independent, we must have $|K| \geq |J|$. $\square$