Expander mixing lemma

The expander mixing lemma intuitively states that the edges of certain $d$-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets $S$ and $T$ is always close to the expected number of edges between them in a random $d$-regular graph, namely $\frac{d}{n}|S||T|$.

d-Regular Expander Graphs

Define an $(n,d,\lambda )$-graph to be a $d$-regular graph $G$ on $n$ vertices such that all of the eigenvalues of its adjacency matrix $A_G$ except one have absolute value at most $\lambda .$ The $d$-regularity of the graph guarantees that its largest absolute value of an eigenvalue is $d.$ In fact, the all-1's vector $\mathbf{𝟏}$ is an eigenvector of $A_G$ with eigenvalue $d$, and the eigenvalues of the adjacency matrix will never exceed the maximum degree of $G$ in absolute value.

If we fix $d$ and $\lambda$ then $(n,d,\lambda )$-graphs form a family of expander graphs with a constant spectral gap.

Statement

Let $G=(V,E)$ be an $(n,d,\lambda )$-graph. For any two subsets $S,T\subseteq V$, let $e(S,T)=|\{(x,y)\in S\times T:xy\in E(G)\}|$ be the number of edges between S and T (counting edges contained in the intersection of S and T twice). Then

$|e(S,T)-\frac{d|S||T|}{n}|\le \lambda \sqrt{|S||T|}.$

Tighter Bound

We can in fact show that

$|e(S,T)-\frac{d|S||T|}{n}|\le \lambda \sqrt{|S||T|(1-|S|/n)(1-|T|/n)}$

using similar techniques.

Biregular Graphs

For biregular graphs, we have the following variation, where we take $\lambda$ to be the second largest eigenvalue.

Let $G=(L,R,E)$ be a bipartite graph such that every vertex in $L$ is adjacent to $d_L$ vertices of $R$ and every vertex in $R$ is adjacent to $d_R$ vertices of $L$. Let $S\subseteq L,T\subseteq R$ with $|S|=\alpha |L|$ and $|T|=\beta |R|$. Let $e(G)=|E(G)|$. Then

$|\frac{e(S,T)}{e(G)}-\alpha \beta |\le \frac{\lambda }{\sqrt{d_L{d}_R}}\sqrt{\alpha \beta (1-\alpha )(1-\beta )}\le \frac{\lambda }{\sqrt{d_L{d}_R}}\sqrt{\alpha \beta }.$

Note that $\sqrt{d_L{d}_R}$ is the largest eigenvalue of $G$.

Proofs

Proof of First Statement

Let $A_G$ be the adjacency matrix of $G$ and let ${\lambda }_1\ge \cdots \ge {\lambda }_n$ be the eigenvalues of $A_G$ (these eigenvalues are real because $A_G$ is symmetric). We know that ${\lambda }_1=d$ with corresponding eigenvector $v_1=\frac{1}{\sqrt{n}}\mathbf{𝟏}$, the normalization of the all-1's vector. Define $\lambda =\sqrt{\max \{{\lambda }_2^2,\dots ,{\lambda }_n^2\}}$ and note that $\max \{{\lambda }_2^2,\dots ,{\lambda }_n^2\}\le {\lambda }^2\le {\lambda }_1^2=d^2$. Because $A_G$ is symmetric, we can pick eigenvectors $v_2,\dots ,v_n$ of $A_G$ corresponding to eigenvalues ${\lambda }_2,\dots ,{\lambda }_n$ so that $\{v_1,\dots ,v_n\}$ forms an orthonormal basis of ${\mathbf{𝐑}}^n$.

Let $J$ be the $n\times n$ matrix of all 1's. Note that $v_1$ is an eigenvector of $J$ with eigenvalue $n$ and each other $v_i$, being perpendicular to $v_1=\mathbf{𝟏}$, is an eigenvector of $J$ with eigenvalue 0. For a vertex subset $U\subseteq V$, let $1_U$ be the column vector with $v^{\text{th}}$ coordinate equal to 1 if $v\in U$ and 0 otherwise. Then,

$|e(S,T)-\frac{d}{n}|S||T||=\left|1_S^{\mathrm{T}}(A_G-\frac{d}{n}J)1_T\right|$.

Let $M=A_G-\frac{d}{n}J$. Because $A_G$ and $J$ share eigenvectors, the eigenvalues of $M$ are $0,{\lambda }_2,\dots ,{\lambda }_n$. By the Cauchy-Schwarz inequality, we have that $|1_S^{\mathrm{T}}M{1}_T|=|1_S\cdot M{1}_T|\le \Vert 1_S\Vert \Vert M{1}_T\Vert$. Furthermore, because $M$ is self-adjoint, we can write

$\Vert M{1}_T{\Vert }^2=⟨M{1}_T,M{1}_T⟩=⟨1_T,M^2{1}_T⟩=⟨1_T,\sum _{i=1}^n{M}^2⟨1_T,v_i⟩v_i⟩=\sum _{i=2}^n{\lambda }_i^2⟨1_T,v_i{⟩}^2\le {\lambda }^2\Vert 1_T{\Vert }^2$.

This implies that $\Vert M{1}_T\Vert \le \lambda \Vert 1_T\Vert$ and $|e(S,T)-\frac{d}{n}|S||T||\le \lambda \Vert 1_S\Vert \Vert 1_T\Vert =\lambda \sqrt{|S||T|}$.

Proof Sketch of Tighter Bound

To show the tighter bound above, we instead consider the vectors $1_S-\frac{|S|}{n}\mathbf{𝟏}$ and $1_T-\frac{|T|}{n}\mathbf{𝟏}$, which are both perpendicular to $v_1$. We can expand

$1_S^{\mathrm{T}}{A}_G{1}_T={\left(\frac{|S|}{n}\mathbf{𝟏}\right)}^{\mathrm{T}}{A}_G\left(\frac{|T|}{n}\mathbf{𝟏}\right)+{(1_S-\frac{|S|}{n}\mathbf{𝟏})}^{\mathrm{T}}{A}_G(1_T-\frac{|T|}{n}\mathbf{𝟏})$

because the other two terms of the expansion are zero. The first term is equal to $\frac{|S||T|}{n^2}{\mathbf{𝟏}}^{\mathrm{T}}{A}_G\mathbf{𝟏}=\frac{d}{n}|S||T|$, so we find that

$|e(S,T)-\frac{d}{n}|S||T||\le \left|{(1_S-\frac{|S|}{n}\mathbf{𝟏})}^{\mathrm{T}}{A}_G(1_T-\frac{|T|}{n}\mathbf{𝟏})\right|$

We can bound the right hand side by $\lambda \Vert 1_S-\frac{|S|}{|n|}\mathbf{𝟏}\Vert \Vert 1_T-\frac{|T|}{|n|}\mathbf{𝟏}\Vert =\lambda \sqrt{|S||T|(1-\frac{|S|}{n})(1-\frac{|T|}{n})}$ using the same methods as in the earlier proof.

Applications

The expander mixing lemma can be used to upper bound the size of an independent set within a graph. In particular, the size of an independent set in an $(n,d,\lambda )$-graph is at most $\lambda n/d.$ This is proved by letting $T=S$ in the statement above and using the fact that $e(S,S)=0.$

An additional consequence is that, if $G$ is an $(n,d,\lambda )$-graph, then its chromatic number $\chi (G)$ is at least $d/\lambda .$ This is because, in a valid graph coloring, the set of vertices of a given color is an independent set. By the above fact, each independent set has size at most $\lambda n/d,$ so at least $d/\lambda$ such sets are needed to cover all of the vertices.

A second application of the expander mixing lemma is to provide an upper bound on the maximum possible size of an independent set within a polarity graph. Given a finite projective plane $\pi$ with a polarity $\perp ,$ the polarity graph is a graph where the vertices are the points a of $\pi$, and vertices $x$ and $y$ are connected if and only if $x\in y^{\perp }.$ In particular, if $\pi$ has order $q,$ then the expander mixing lemma can show that an independent set in the polarity graph can have size at most $q^{3/2}-q+2q^{1/2}-1,$ a bound proved by Hobart and Williford.

Converse

Bilu and Linial showed that a converse holds as well: if a $d$-regular graph $G=(V,E)$ satisfies that for any two subsets $S,T\subseteq V$ with $S\cap T=\mathrm{\varnothing }$ we have

$|e(S,T)-\frac{d|S||T|}{n}|\le \lambda \sqrt{|S||T|},$

then its second-largest (in absolute value) eigenvalue is bounded by $O(\lambda (1+\log (d/\lambda )))$.

Generalization to hypergraphs

Friedman and Widgerson proved the following generalization of the mixing lemma to hypergraphs.

Let $H$ be a $k$-uniform hypergraph, i.e. a hypergraph in which every "edge" is a tuple of $k$ vertices. For any choice of subsets $V_1,...,V_k$ of vertices,

$||e(V_1,...,V_k)|-\frac{k!|E(H)|}{n^k}|V_1|...|V_k||\le {\lambda }_2(H)\sqrt{|V_1|...|V_k|}.$

References

• Alon, N.; Chung, F. R. K. (1988), "Explicit construction of linear sized tolerant networks", Discrete Mathematics 72 (1–3): 15–19, doi:10.1016/0012-365X(88)90189-6 .
• F.C. Bussemaker, D.M. Cvetković, J.J. Seidel. Graphs related to exceptional root systems, Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), volume 18 of Colloq. Math. Soc. János Bolyai (1978), 185-191.

• Haemers, W. H. (1979). Eigenvalue Techniques in Design and Graph Theory (PDF) (Ph.D.).
• Haemers, W. H. (1995), "Interlacing Eigenvalues and Graphs", Linear Algebra Appl. 226: 593–616, doi:10.1016/0024-3795(95)00199-2, https://research.tilburguniversity.edu/en/publications/8fe72c7b-43cc-455a-a229-1833455b7746 .

• Hoory, S.; Linial, N.; Wigderson, A. (2006), "Expander Graphs and their Applications", Bull. Amer. Math. Soc. (N.S.) 43 (4): 439–561, doi:10.1090/S0273-0979-06-01126-8, http://www.cc.gatech.edu/~mihail/LINIALexpsurvey.pdf .

• Friedman, J.; Widgerson, A. (1995), "On the second eigenvalue of hypergraphs", Combinatorica 15 (1): 43–65, doi:10.1007/BF01294459, https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/FW95/fw95a.pdf .