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 $\lambda \in (0,d)$ the second-largest eigenvalue (in absolute value) of the adjacency matrix. 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

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

For biregular graphs, we have the following variation.

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

$\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 ${\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 $|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 $A|V\rangle =d|V\rangle$, and the number of edges between $S$ and $T$ is given by $E(S,T)=\langle S|A|T\rangle$.

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

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

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

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

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

The conclusion follows, since $\langle V|A|V\rangle =d\||V\rangle \|^{2}=dn$, and $|\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 that the converse holds as well: if a graph satisfies the conclusion of the expander mixing lemma, that is, for any two subsets $S,T\subseteq V$,

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

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

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.