The expander mixing lemma intuitively states that the edges of certain
after-content-x4
-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets
and
is always close to the expected number of edges between them in a random
-regular graph, namely
.
Table of Contents
after-content-x4
d-Regular Expander Graphs[edit]
Define an
-graph to be a
-regular graph
on
vertices such that all of the eigenvalues of its adjacency matrix
except one have absolute value at most
The
-regularity of the graph guarantees that its largest absolute value of an eigenvalue is
In fact, the all-1’s vector
is an eigenvector of
with eigenvalue
, and the eigenvalues of the adjacency matrix will never exceed the maximum degree of
in absolute value.
If we fix
and
then
-graphs form a family of expander graphs with a constant spectral gap.
Statement[edit]
Let
be an
-graph. 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
Tighter Bound[edit]
We can in fact show that
using similar techniques.[1]
Biregular Graphs[edit]
For biregular graphs, we have the following variation, where we take
to be the second largest eigenvalue.[2]
Let
be a bipartite graph such that every vertex in
is adjacent to
vertices of
and every vertex in
is adjacent to
vertices of
. Let
with
and
. Let
. Then
Note that
is the largest eigenvalue of
.
Proof of First Statement[edit]
Let
be the adjacency matrix of
and let
be the eigenvalues of
(these eigenvalues are real because
is symmetric). We know that
with corresponding eigenvector
, the normalization of the all-1’s vector. Define
and note that
. Because
is symmetric, we can pick eigenvectors
of
corresponding to eigenvalues
so that
forms an orthonormal basis of
.
Let
be the
matrix of all 1’s. Note that
is an eigenvector of
with eigenvalue
and each other
, being perpendicular to
, is an eigenvector of
with eigenvalue 0. For a vertex subset
, let
be the column vector with
coordinate equal to 1 if
and 0 otherwise. Then,
.
Let
. Because
and
share eigenvectors, the eigenvalues of
are
. By the Cauchy-Schwarz inequality, we have that
. Furthermore, because
is self-adjoint, we can write
.
This implies that
and
.
Proof Sketch of Tighter Bound[edit]
To show the tighter bound above, we instead consider the vectors
and
, which are both perpendicular to
. We can expand
because the other two terms of the expansion are zero. The first term is equal to
, so we find that
We can bound the right hand side by
using the same methods as in the earlier proof.
Applications[edit]
The expander mixing lemma can be used to upper bound the size of an independent set within a graph. In particular, the size of an independent set in an
-graph is at most
This is proved by letting
in the statement above and using the fact that
An additional consequence is that, if
is an
-graph, then its chromatic number
is at least
This is because, in a valid graph coloring, the set of vertices of a given color is an independent set. By the above fact, each independent set has size at most
so at least
such sets are needed to cover all of the vertices.
A second application of the expander mixing lemma is to provide an upper bound on the maximum possible size of an independent set within a polarity graph. Given a finite projective plane
with a polarity
the polarity graph is a graph where the vertices are the points a of
, and vertices
and
are connected if and only if
In particular, if
has order
then the expander mixing lemma can show that an independent set in the polarity graph can have size at most
a bound proved by Hobart and Williford.
Converse[edit]
Bilu and Linial showed[3] that a converse holds as well: if a
-regular graph
satisfies that for any two subsets
with
we have
then its second-largest (in absolute value) eigenvalue is bounded by
.
Generalization to hypergraphs[edit]
Friedman and Widgerson proved the following generalization of the mixing lemma to hypergraphs.
Let
be a
-uniform hypergraph, i.e. a hypergraph in which every “edge” is a tuple of
vertices. For any choice of subsets
of vertices,
References[edit]
Alon, N.; Chung, F. R. K. (1988), “Explicit construction of linear sized tolerant networks”, Discrete Mathematics, 72 (1–3): 15–19, doi:10.1016/0012-365X(88)90189-6.
Recent Comments