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 .
Read the rest of this entry »