Expander mixing lemma
The expander mixing lemma states that, for any two subsets of a d-regular expander graph
with
vertices, the number of edges between
and
is approximately what you would expect in a random d-regular graph, i.e.
.
Statement
Let be a d-regular graph on n vertices with
the second-largest eigenvalue (in absolute value) of the normalized adjacency matrix. For any two subsets
, let
be the number of edges between S and T (counting edges contained in the intersection of S and T twice).
Then
Proof
Let be the adjacency matrix for
. For a vertex subset
, let
. Here
is the standard basis element of
with a one in the
position. Thus in particular
, and the number of edges between
and
is given by
.
Expand each of and
into a component in the direction of the largest-eigenvalue eigenvector
and an orthogonal component:
,
where . Then
.
The conclusion follows, since , and
.
Converse
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 ,
then its second-largest eigenvalue is .