Definitions

# Expander mixing lemma

The expander mixing lemma states that, for any two subsets $S, T$ of a 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 |S| cdot |T| / n$.

## Statement

Let $G = \left(V, E\right)$ be a d-regular graph with (un-)normalized second-largest eigenvalue $lambda$. Then for any two subsets $S, T subseteq V$, let $E\left(S, T\right)$ denote the number of edges between S and T. We have

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

For a proof, see link in 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\left(S, T\right) - frac\left\{d |S| cdot |T\left\{n\right\}| leq alpha sqrt$
>

then its second-largest eigenvalue is $O\left(alpha\left(1+log\left(d/alpha\right)\right)\right)$.

## References

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

Search another word or see Expander Mixing Lemmaon Dictionary | Thesaurus |Spanish