expander mixing lemma

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 ${G=(V,E)}$ is a ${d}$ -regular undirected graph, and ${A}$ is its adjacency matrix. Then let the eigenvalues of the normalized matrix ${\frac 1d A}$ be

$\displaystyle 1 = \lambda_1 \geq \lambda_2 \geq \cdots \geq \lambda_n$

We are interested in graphs for which all the eigenvalues are small in absolute value, except ${\lambda_1}$ , that is, if we define

$\displaystyle \sigma_2 := \max\{ |\lambda_2|, |\lambda_3 | , \ldots , | \lambda_n | \}$

we are interested in graphs for which ${\sigma_2}$ is small. The expander mixing lemma is the fact that for every two disjoint sets ${S}$ and ${T}$ of vertices we have

$\displaystyle \left | E(S,V-S) - \frac d n \cdot |S| \cdot |T| \right | \leq \sigma_2 d \sqrt{ |S| \cdot |T|} \ \ \ \ \ (1)$

The inequality (1) says that, if ${\sigma_2}$ 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 ${d}$ -regular graph, up to an error term that depends on ${\sigma_2}$ .

For the proof, we observe that, if we call ${J}$ the matrix that has ones everywhere, then

$\displaystyle \sigma_2 = \max_{x \perp (1,\ldots , 1) } \frac { |x^T A x|}{d\cdot x^Tx} = \max_{x} \frac { \left|x^T \left( A - \frac dn J \right) x \right|}{d\cdot x^T x} = \max_{x,y} \frac { \left|x^T \left( A - \frac dn J \right) y \right|}{d\cdot ||x|| \cdot ||y||}$

and then we substitute ${x := {\mathbf 1}_S}$ and ${y:= {\mathbf 1}_T}$ in the above expression and do the calculations.

In the case of an irregular undirected graph ${G=(V,E)}$ , we are going to consider the normalized adjacency matrix ${M:= D^{-\frac 12} A D^{-\frac 12 }}$ , where ${A}$ is the adjacency matrix of ${G}$ and ${D}$ is the diagonal matrix such that ${D_{v,v} = d_v}$ , where ${d_v}$ is the degree of ${v}$ . As in the regular case, the eigenvalues of the normalized adjacency matrix satisfy

$\displaystyle 1 = \lambda_1 \geq \lambda_2 \geq \cdots \lambda_n \geq -1$

Let us define

$\displaystyle \sigma_2:= \max \{ |\lambda_2| , |\lambda_3| , \ldots, |\lambda_n| \}$

the second largest eigenvalue in absolute value of ${M}$ .

We will need two more definitions: for a set of vertices ${S}$ , its volume is defined as

$\displaystyle vol(S):= \sum_{v\in S} d_v$

the sum of the degrees and ${\bar d = \frac 1n \sum_v d_v}$ the average degree, so that ${vol(V) = \bar d n }$ . Now we have

Lemma 1 (Expander Mixing Lemma) For every two disjoint sets of vertices ${S}$ , ${T}$ , we have

$\displaystyle \left | E(S,V-S) - \frac {vol(S) \cdot vol(T) }{vol(V)} \right | \leq \sigma_2 \sqrt{vol(S) \cdot vol(T) } \ \ \ \ \ (2)$

So, once again, we have that the number of edges between ${S}$ and ${T}$ is what one would expect in a random graph in which the edge ${(u,v)}$ exists with probability ${d_ud_v/vol(V)}$ , up to an error that depends on ${\sigma_2}$ .

Continue reading →

in theory

"Marge, I agree with you – in theory. In theory, communism works. In theory." — Homer Simpson

Tag Archives: expander mixing lemma

CS294 Lecture 20: Properties of Expanders

The Expander Mixing Lemma in Irregular Graphs