*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 .