4
$\begingroup$

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.$

$\endgroup$
  • $\begingroup$ I struggled a bit ascertaining the precise compatibility condition between the graph and the matrix/weighting. Are you assuming that matrix $U$ has zeros along the diagonal, as appears to be the case from the proof? If so, an easy trace argument shows that the eigenvalue multiplicities of $1$ and $-1$ are equal, hence the graph has an even number of vertices. $\endgroup$ – Victor Protsak Aug 5 '19 at 19:05
  • $\begingroup$ Another trivial observation is that the existence of a hermitian/unitary weighting (HUW) for $G$ is equivalent to the existence of HUW for each connected component of $G$, thus the question reduces to the connected graph case. In particular, a necessary condition for the existence of an HUW is that each connected component of the graph have an even number of vertices. $\endgroup$ – Victor Protsak Aug 5 '19 at 19:44
  • $\begingroup$ @VictorProtsak Thanks! That was a feature of the Huang matrices and I didn't think checking whether it was necessary since I didn't need the hypothesis. Note that adding a loop outside $H$ would still make the argument work, so I'm not sure whether the diagonal should be assumed to be zero. $\endgroup$ – François G. Dorais Aug 6 '19 at 2:28
  • $\begingroup$ Perhaps this also means that $G$ must be bipartite? All odd powers of $U$ have zero trace. This is necessarily true if $G$ has no odd cycles. Perhaps this is the only case? $\endgroup$ – François G. Dorais Aug 6 '19 at 3:51
  • $\begingroup$ The first question seems to be addressed in [1] for unitary weightings. [1] Severini, Simone. "On the digraph of a unitary matrix." SIAM Journal on Matrix Analysis and Applications 25.1 (2003): 295-300. $\endgroup$ – smapers Aug 6 '19 at 13:23
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ I have also proved this property. Note, however, that this proof employs a weaker notion of compatibility between the graph and the weighting than in the question: the support of the $V\times V$ matrix $U$ is contained in the edge set $E$, rather than equal to it, --- in fact beyond $|V|=2$, the construction always produces a disconnected support graph. Interestingly enough, there are non-trivial restrictions on connected $G$ with strongly compatible weightings. For example, for $m=2$, only the complete bipartite graph $K_{2,2}$ is possible, and for $m=3, |K_{3,,3}-G|\leq 1$. $\endgroup$ – Victor Protsak Aug 8 '19 at 6:40
  • $\begingroup$ (CONT'd) This, in particular, forbids the bipartite cycle graph $C_6.$ Additionally, I have checked by a brute force calculation that for the smallest non-trivial size $|V|=4$, any connected $G$ must be bipartite, so that for example the complete graph $K_4$ cannot be realized, providing some evidence for your bipariteness conjecture in the comments. (Strictly speaking, I only considered symmetric orthogonal matrices, so I'd need to check that the proofs carry over to the HU case.) $\endgroup$ – Victor Protsak Aug 8 '19 at 7:04
  • $\begingroup$ In fact, one can realize some of these "impossible" graphs by allowing arbitrary diagonal entries, as is common in the vast literature on the Inverse Eigenvalue Problem, minimal rank, etc. (The lower bound on the maxdegree becomes: $|\lambda_1|-{\rm max}|u_{ii}|$ divided by ${\rm max}|u_{ij}|, i\ne j$.) However, not every graph is realizable, and an obvious obstruction is given by the independence number of $G$. E.g. take a complete bipartite graph $K_{p,q}, p>q$ and connect some pairs of $q$ red vertices. The set of $H$ of $p$ black vertices violates the conclusion of the theorem. $\endgroup$ – Victor Protsak Aug 8 '19 at 7:46
  • $\begingroup$ Thanks again @VictorProtsak! I had also noticed the issue with cycles. In general, any two vertices $u_1,u_2$ such that there is exactly one $v$ that is connected to both will produce a $0$ where it wasn't necessary. This generalizes, if there are $u_1,\ldots,u_n$ and $v_1,\ldots,v_m$ such that for every pair $1 \leq i < j \leq n$, the only vertices connected to both $u_i,u_j$ are among $v_1,\ldots,v_m$ and each $u_i$ is connected to at least one $v_i$, The vectors $x_i = (w(u_i,v_1),\ldots,w(u_i,v_m)) \in {\mathbb C}^m$ must be orthogonal, so if $n > m$ at least one of these will be $0$. $\endgroup$ – François G. Dorais Aug 8 '19 at 8:32
  • $\begingroup$ On the other hand, if for every $i=1,\ldots,n$ the set $\{j < i | \exists k,(v_j,v_{m+k}),(v_i,v_{m+k}) \in E \}$ always has size less than the degree of $v_i$, then we can use a modified Gram-Schmidt to get a weighting with exact support. $\endgroup$ – François G. Dorais Aug 8 '19 at 8:39

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.