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

## Statement

Let $G = (V, E)$ be a d-regular graph on $n$ vertices with $\lambda\in(0,1)$ 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

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| \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

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

• Expander mixing lemma converse. [1]