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

Frequently asked questions

Doesn't flipping some signs to

-1

change how large the eigenvalue can be?

It changes the exact eigenvalues, but the row-sum bound only uses absolute values of entries, so the inequality $\lambda_1(A) \le \Delta(H)$ holds regardless of the signs chosen; this is precisely why Huang is free to design the clever signs of $A_n$ without breaking Lemma 2.3.

Source

Hao Huang, 2019

Induced subgraphs of hypercubes and a proof of the Sensitivity Conjecture

arXiv:1907.00847v1

Step 4 of 7: A general fact: row sums bound eigenvalues

Previous step Next step

In plain words

For any graph, however it is coloured with signs $+1$ and $-1$ on its edges, the biggest eigenvalue of the resulting matrix can never exceed the largest number of edges meeting any single vertex. Intuitively, an eigenvector equation forces a weighted balance at each coordinate, and that balance cannot outrun the number of neighbours contributing to it.

\Delta(H) \ge \lambda_1 := \lambda_1(A)

Detailed analysis

Huang (2019, Lemma 2.3) proves a simple but crucial fact: if $H$ is an $m$ -vertex graph and $A$ is any symmetric matrix with entries in $\{-1,0,1\}$ whose nonzero pattern matches the edges of $H$ , then $\Delta(H) \ge \lambda_1 := \lambda_1(A)$ . The proof picks the eigenvector $v$ for the top eigenvalue and looks at the coordinate $v_1$ of largest absolute value: since $|\lambda_1 v_1| = |(Av)_1| = \left|\sum_{j \sim 1} A_{1,j} v_j\right| \le \Delta(H)|v_1|$ , dividing by $|v_1|$ gives $\lambda_1(A) \le \Delta(H)$ .

Terms in this step

Eigenvector: A nonzero vector $v$ with $Av = \lambda v$ for the eigenvalue $\lambda$ ; the direction $v$ is left unchanged (only rescaled) by the matrix $A$ .

Knowledge used in this step

Eigenvalues and diagonalization