Eigenvalue gaps allow us to upper bound the rate of convergence of random walks on graphs.

In this note, we will look at the connection between the eigenvalue gap and a combinatorial graph parameter, called “expansion”"

Let $$G$$ be a $$d$$-regular graph with $$n$$ vertices. We identify $$G$$ with its random-walk matrix (normalized adjacency matrix).

Definition: The eigenvalue gap of $$G$$ is defined as $\gamma(G)=\min_{f\bot u} \frac{\langle f,L_G f\rangle }{\|f\|_2^2},$ where $$L_G=I-G$$ is the Laplacian of $$G$$.

Exercise: Check that $$\gamma(G)=\lambda_1(G)-\lambda_2(G)$$ is indeed the gap between the largest and second largest eigenvalue of $$G$$.

We would like to characterize the eigenvalue gap of a graph in terms of a combinatorial property. The right combinatorial property turns out to be expansion, which measures how well $$G$$ is connected.

Definition: The expansion of $$G$$ is defined as $\phi(G) = \min_{S\subseteq V,~|S|\le n/2} \frac{\tfrac1d |E(S,\bar S)|}{|S|}.$ (Here, $$E(S,\bar S)$$ is the set of edges from $$S$$ to $$\bar S$$.) The quantity $$\phi(S)=\tfrac1d|E(S,\bar S)|/|S|$$ is the expansion of $$S$$.

Exercise: Check that ${\langle f,L_G f\rangle} = \sum_i \E_{j\sim i}\tfrac12(f_i-f_j)^2.$ (So the Laplacian exactly measures how close the values of $$f$$ are for a typical edge of the graph.)

It follows that $${\langle 1_S,L_G 1_S\rangle}=\tfrac1d |E(S,\bar S)|$$ and therefore $\phi(G) = \min_{S\subseteq V,~|S|\le n/2} {\langle 1_S,L_G 1_S\rangle}/{\|1_S\|_2^2}.$

Cheeger’s inequality asserts that $$\gamma(G)$$ is the same as $$\phi(G)$$ up to quadratic factor.

Theorem: (Cheeger’s inequality) $\gamma(G)/2 \le \phi(G) \le 2\sqrt{\gamma(G)}.$

The following direction is the easier one.

Lemma: $$\phi(G)\ge \gamma(G)/2$$

Proof: Let $$S$$ be a subset of vertices with $$|S|\le n/2$$. We like to lower bound its expansion. Let $$p=1_S/|S|$$ be the uniform distribution over $$S$$. Then $$p=u+f$$, where $$u$$ is the uniform distribution and $$f$$ is orthogonal to $$u$$. Then, $\phi(S) = \frac{\langle p,L_G p\rangle}{\|p\|_2^2} %\frac{\langle u,L_G u\rangle+\langle f,L_G f\rangle}{\|u\|_2^2+\|f\|_2^2} =\frac{\langle f,L_G f\rangle}{\|u\|_2^2+\|f\|_2^2} \ge \frac{\gamma\|f\|_2^2}{\|u\|_2^2+\|f\|_2^2}.$

To finish the proof, it is enough to show that $$\|f\|_2^2 \ge \|u\|_2^2$$. (This means that the distribution $$p$$ is “far” from $$u$$.) Recall that $$f=1_S/|S|-u$$. It follows that the distance of $$1_S/|S|$$ and $$u$$ decreases as the size of $$S$$ grows. Hence, the distance is smallest if $$|S|=n/2$$. In this case, $$f$$ takes values $$\pm 1/n$$. Hence, $$\|f\|_2^2=n\cdot 1/n^2=1/n=\|u\|_2^2$$.

Next, we will prove the other direction of Cheeger’s inequality.

The first step is the following lemma (which we have seen in class).

Lemma: Suppose $$h$$ is a function with $$|\mathrm{supp}(h)|\le n/2$$ and $$\langle h,L_G h\rangle\le \epsilon\|h\|_2^2$$. Then there exists a set $$S$$ with $$|S|\le n/2$$ and $$\phi(S)\le \sqrt{2\epsilon}$$.

W.l.o.g. we may assume $$0\le h\le 1$$. The main idea is to construct a distribution over sets $$S$$ by choosing a random threshold $$\tau\in[0,1]$$ and setting $$S=\{i \mid h_i^2>\tau\}$$. It is easy to verify that $$\E_S |S|=\|h\|_2^2$$. Using Cauchy-Schwarz, one can also show $$\E_S \tfrac1d|E(S,\bar S)|\le \sqrt{2\epsilon}\|h\|_2^2$$. Hence, there exists a set in the support of the distribution with expansion at most $$\sqrt{2\epsilon}$$.

The next step is to construct such a function $$h$$.

Lemma: There exists a function $$h$$ with $$|\mathrm{supp}(h)|\le n/2$$ and $$\langle h,L_G h\rangle\le 2\gamma(G)\|h\|_2^2$$.

Proof: Let $$f$$ be a function such that $$f\bot u$$ and $$\langle f,L_G f\rangle \le \gamma(G)\|f\|_2^2$$. Let $$m$$ be the median of this function. (So that $$f$$ has value larger than $$m$$ for exactly half of the vertices.) Let $$h_1=(f-m)_+$$ be the positive part of $$f-m$$ and let $$h_2=(f-m)_{-}$$ be the negative part of $$f-m$$. Notice that both $$h_1$$ and $$h_2$$ have exactly half of the vertices in their support. We claim that one of the functions $$h_1,h_2$$ satisfies also the other condition of the lemma.

Indeed, we can see that $$\langle h_1,L_G h_1\rangle \le \langle f,L_G f\rangle$$ and $$\langle h_2,L_G h_2\rangle\le \langle f,L_G f\rangle$$. On the other hand, $$\|f\|_2^2=\|h_1\|_2^2+\|h_2\|^2$$. Hence, we can choose $$h$$ to be the function $$h_1$$ or $$h_2$$ with larger norm.