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.^[1]

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^[2] 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 )))$ .

Notes

↑ See Theorem 5.1 in "Interlacing Eigenvalues and Graphs" by Haemers
↑ 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 .

This article is issued from Wikipedia - version of the 11/10/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.