Expander mixing lemma

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

Statement

Let ${\displaystyle 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|(1-|S|/n)(1-|T|/n)}}\,.}$

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

Let ${\displaystyle G=(L,R,E)}$ be a bipartite graph such that every vertex in ${\displaystyle L}$ is adjacent to ${\displaystyle d_{L}}$ vertices of ${\displaystyle R}$ and every vertex in ${\displaystyle R}$ is adjacent to ${\displaystyle d_{R}}$ vertices of ${\displaystyle 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 ${\displaystyle G}$.

Proof

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

Expand each of ${\displaystyle |S\rangle }$ and ${\displaystyle |T\rangle }$ into a component in the direction of the largest-eigenvalue eigenvector ${\displaystyle |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}$. This orthogonality implies that ${\displaystyle \||S\rangle \|^{2}=\|{\frac {|S|}{n}}|V\rangle \|^{2}+\||S'\rangle \|^{2}}$ and ${\displaystyle \||T\rangle \|^{2}=\|{\frac {|T|}{n}}|V\rangle \|^{2}+\||T'\rangle \|^{2}}$. Moreover

${\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 \||S'\rangle \|\cdot \|A|T'\rangle \|\leq \lambda \||S'\rangle \|\||T'\rangle \|=\lambda {\sqrt {\||S\rangle \|^{2}-\|{\frac {|S|}{n}}|V\rangle \|^{2}}}{\sqrt {\||T\rangle \|^{2}-\|{\frac {|T|}{n}}|V\rangle \|^{2}}}=\lambda {\sqrt {|S|(1-|S|/n)|T|(1-|T|/n)}}}$.

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 (1–3): 15–19, doi:10.1016/0012-365X(88)90189-6.