Expander mixing lemma

The expander mixing lemma states that, for any two subsets $S,T$ of a d-regular expander graph $G$ with $n$ vertices, the number of edges between $S$ and $T$ is approximately what you would expect in a random d-regular graph, i.e. $d|S||T|/n$.

Statement

Let $G=(V,E)$ be a d-regular graph on n vertices with ${\displaystyle \lambda \in (0,d)}$ the second-largest eigenvalue (in absolute value) of the adjacency matrix. For any two subsets ${\displaystyle S,T\subseteq V}$, let ${\displaystyle 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

${\displaystyle \left|e(S,T)-{\frac {d|S||T|}{n}}\right|\leq \lambda {\sqrt {|S||T|}}\,.}$

For biregular graphs, we have the following variation.^[1]

Let ${\displaystyle 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 ${\displaystyle d_{R}}$ vertices of $L$. Let ${\displaystyle S\subseteq L,T\subseteq R}$ with ${\displaystyle |S|=\alpha |L|}$ and ${\displaystyle |T|=\beta |R|}$. Let ${\displaystyle e(G)=|E(G)|}$. Then

${\displaystyle \left|{\frac {e(S,T)}{e(G)}}-\alpha \beta \right|\leq {\frac {\lambda }{\sqrt {d_{L}d_{R}}}}{\sqrt {\alpha \beta (1-\alpha )(1-\beta )}}\leq {\frac {\lambda }{\sqrt {d_{L}d_{R}}}}{\sqrt {\alpha \beta }}\,.}$

Note that ${\displaystyle {\sqrt {d_{L}d_{R}}}}$ is the largest absolute value of the eigenvalues of $G$.

Proof

Let $A$ be the adjacency matrix for $G$. For a vertex subset $U\subseteq V$, let ${\displaystyle |U\rangle =\sum _{v\in U}|v\rangle \in \mathbf {R} ^{n}}$. Here $|v\rangle$ is the standard basis element of $\mathbf {R} ^{n}$ with a one in the $v^{th}$ position. Thus in particular ${\displaystyle A|V\rangle =d|V\rangle }$, and the number of edges between $S$ and $T$ is given by ${\displaystyle E(S,T)=\langle S|A|T\rangle }$.

Expand each of $|S\rangle$ and ${\displaystyle |T\rangle }$ into a component in the direction of the largest-eigenvalue eigenvector $|V\rangle$ and an orthogonal component:

${\displaystyle |S\rangle ={\frac {|S|}{n}}|V\rangle +|S'\rangle }$

${\displaystyle |T\rangle ={\frac {|T|}{n}}|V\rangle +|T'\rangle }$,

where ${\displaystyle \langle S'|V\rangle =\langle T'|V\rangle =0}$. Then

${\displaystyle \langle S|A|T\rangle ={\frac {|S||T|}{n^{2}}}\langle V|A|V\rangle +\langle S'|A|T'\rangle }$.

The conclusion follows, since ${\displaystyle \langle V|A|V\rangle =d\||V\rangle \|^{2}=dn}$, and ${\displaystyle |\langle S'|A|T'\rangle |\leq d\lambda ||S'\rangle .|T'\rangle |\leq d\lambda \||S'\rangle \|\||T'\rangle \|\leq d\lambda \||S\rangle \|\||T\rangle \|=d\lambda {\sqrt {|S||T|}}}$.

Converse

Bilu and Linial showed^[2] that the converse holds as well: if a graph satisfies the conclusion of the expander mixing lemma, that is, for any two subsets ${\displaystyle S,T\subseteq V}$,

${\displaystyle |E(S,T)-{\frac {d|S||T|}{n}}|\leq d\lambda {\sqrt {|S||T|}}}$

then its second-largest eigenvalue is ${\displaystyle O(d\lambda (1+\log(1/\lambda )))}$.

Notes

1. See Theorem 5.1 in "Interlacing Eigenvalues and Graphs" by Haemers
2. Expander mixing lemma converse.

References

• Alon, N.; Chung, F. R. K. (1988), "Explicit construction of linear sized tolerant networks", Discrete Mathematics, 72: 15–19, doi:10.1016/0012-365X(88)90189-6.

• Haemers, W. H. (1979). "3". 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.

• Hoory, S.; Linial, N.; Wigderson, A. (2006), "Expander Graphs and their Applications" (PDF), Bull. Amer. Math. Soc. (N.S.), 43: 439–561, doi:10.1090/S0273-0979-06-01126-8.