In which we prove properties of expander graphs.
Tag Archives: expander mixing lemma
The Expander Mixing Lemma in Irregular Graphs
Today, after a lecture in the spectral graph theory boot camp at the Simons institute, I was asked what the expander mixing lemma is like in graphs that are not regular.
I don’t know if I will have time to return to this tomorrow, so here is a quick answer.
First, for context, the expander mixing lemma in regular graph. Say that is a
-regular undirected graph, and
is its adjacency matrix. Then let the eigenvalues of the normalized matrix
be
We are interested in graphs for which all the eigenvalues are small in absolute value, except , that is, if we define
we are interested in graphs for which is small. The expander mixing lemma is the fact that for every two disjoint sets
and
of vertices we have
The inequality (1) says that, if is small, then the number of edges between every two large sets of vertices is almost determined just by the size of the sets, and it is equal to the expected number of edges between the two sets in a random
-regular graph, up to an error term that depends on
.
For the proof, we observe that, if we call the matrix that has ones everywhere, then
and then we substitute and
in the above expression and do the calculations.
In the case of an irregular undirected graph , we are going to consider the normalized adjacency matrix
, where
is the adjacency matrix of
and
is the diagonal matrix such that
, where
is the degree of
. As in the regular case, the eigenvalues of the normalized adjacency matrix satisfy
Let us define
the second largest eigenvalue in absolute value of .
We will need two more definitions: for a set of vertices , its volume is defined as
the sum of the degrees and the average degree, so that
. Now we have
Lemma 1 (Expander Mixing Lemma) For every two disjoint sets of vertices
,
, we have
So, once again, we have that the number of edges between and
is what one would expect in a random graph in which the edge
exists with probability
, up to an error that depends on
.