Expander mixing lemma

From Wikipedia, the free encyclopedia

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

Statement

Let $G=(V,E)$ be a d-regular graph with normalized second-largest eigenvalue $\lambda$ (in absolute value) of the adjacency matrix. Then for any two subsets $S,T\subseteq V$ , let $E(S,T)$ denote the number of edges between S and T. If the two sets are not disjoint, edges in their intersection are counted twice, that is, $E(S,T)=2|E(G[S\cap T])|+E(S\setminus T,T)+E(S,T\setminus S)$ . We have

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

For a proof, see references.

Converse

Recently, 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\cdot |S|\cdot |T|}{n}}|\leq d\lambda {\sqrt {|S|\cdot |T|}}$

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

References

Notes proving the expander mixing lemma.
Expander mixing lemma converse.

This article is issued from Wikipedia. The text is available under the Creative Commons Attribution/Share Alike; additional terms may apply for the media files.