Expander mixing lemma

From Wikipedia, the free encyclopedia
Jump to: navigation, search

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 \cdot|S| \cdot |T| / n.

Statement[edit]

Let G = (V, E) be a d-regular graph on n vertices with \lambda the second-largest eigenvalue (in absolute value) of the normalized 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|}\,.

Proof[edit]

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. 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| \cdot |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 = d n, and | \langle S' | A | T' \rangle | \leq d \lambda \| | S' \rangle \| \cdot \| | T' \rangle \| \leq d \lambda \| | S \rangle \| \cdot \| | T \rangle \| = d \lambda \sqrt{|S| |T|}.

Converse[edit]

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[edit]

  • Expander mixing lemma converse. [1]