March 30, 2012

Agenda

Our agenda for the next few weeks looks something like this:

The discrete Cheeger inequality
The connection between ${\lambda_2}$ and the mixing time of random walks
Planar separators, eigenvalues, and circle packings
Expander graphs and rapid mixing
The small-set expansion problem and the Unique Games Conjecture
Higher-order Cheeger inequalities
Cheeger inequalities for very large eigenvalues (Arora-Barak-Steurer)
Mixing times and the spectral profile

Posted in Announcement
Leave a comment

March 29, 2012

Remarks on Lecture 2

In this lecture, we generalized our setting to weighted graphs ${G=(V,E,w)}$ where ${w : E \to \mathbb R^+}$ is a positive weight function on edges. We also looked at the basic spectral theory of the normalized Laplacian, defined by

${\mathcal L_G = I - D_G^{-1/2} A_G D_G^{-1/2}}$ ,

which operates on functions ${f : V \to \mathbb R}$ via

$\mathcal L_G f(u) = f(u) - \sum_{v \sim u} \frac{w(u,v)}{\sqrt{w(u) w(v)}} f(v)$ .

In particular, we associated with ${\mathcal L_G}$ the normalized Rayleigh quotient,

$\mathcal R_G(f) = \frac{\sum_{u \sim v} w(u,v) (f(u)-f(v))^2}{\sum_{u \in V} w(u) f(u)^2}$ ,

and we showed that we can express the second-smallest eigenvalue as

${\lambda_2(\mathcal L_G) = \min \{ \mathcal R_G(f) : \sum_{v \in V} w(v) f(v) = 0 \}}$ .

We defined the expansion of a subset ${S \subseteq V}$ by

${\phi_G(S) = \mathcal R_G(\mathbf{1}_S)}$ ,

where ${\mathbf{1}_S}$ is the characteristic function for ${S}$ .

Finally, we defined the expansion of a graph by

${\Phi_G = \min \left\{ \phi_G(S) : 0 < w(S) < w(V)/2\right\}}$

We then stated and (almost) proved the following discrete Cheeger inequality.

Theorem 1. For any weighted graph ${G=(V,E,w)}$ , we have

$\frac{\lambda_2}{2} \leq \Phi_G \leq 2 \sqrt{\lambda_2}$ ,

where ${\lambda_2 = \lambda_2(\mathcal L_G)}$ .

Exercises (optional)

Prove that for the normalized Laplacian, just as for the combinatorial Laplacian, the number of connected components in a graph G is precisely the multiplicity of the smallest eigenvalue.

We saw the the right-hand inequality in Theorem 1 is asymptotically tight. Prove that the left-hand side is asymptotically tight for the complete graph on n nodes.

Posted in Notes
5 Comments

March 27, 2012

Remarks on Lecture 1

Today we started studying the spectrum of the combinatorial Laplacian on a graph $G=(V,E)$ . This is the operator $L_G : \mathbb R^V \to \mathbb R^V$ given by

$L_G f(x) = \mathrm{deg}(x) f(x) - \sum_{y \sim x} f(y)\,.$

We saw that $L_G$ has a spectrum of the form $0 = \lambda_1 \leq \lambda_2 \leq \cdots \leq \lambda_n$ , and that the number of connected components in $G$ is precisely the multiplicity of $\lambda_1$ .

I encourage you to look at the first four lectures of Spielman’s course for a refresher.

Exercises

The best way to learn a subject is to get your hands dirty. Here are some optional exercises to help build your intuition.

Recall that for a function $f : V \to \mathbb R$ , we define its Rayleigh quotient by

$\displaystyle \mathcal R_G(f) = \frac{\sum_{x \sim y} (f(x)-f(y))^2}{\sum_{x \in V} f(x)^2}.$

If $P_n$ is the path graph on n vertices, then as we argued today, we have $\lambda_k \asymp \left(\frac{k}{n}\right)^2$ .

Prove that $\lambda_2 \asymp \frac{1}{n^2}$ by showing that (a) there exists a map $f : V \to \mathbb R$ with $f \perp \mathbf{1}$ and $\mathcal R_G(f) \lesssim \frac{1}{n^2}$ and (b) for any such map with $f \perp \mathbf{1}$ , we have $\mathcal R_G(f) \gtrsim \frac{1}{n^2}$ . We did this in class, but it will help to reconstruct the proof on your own.
Try to prove that $\lambda_k \lesssim \left(\frac{k}{n}\right)^2$ by exhibiting an explicit subspace of test functions
that achieves this bound. It may help to use the Courant-Fischer min-max principle
which says that

$\displaystyle \lambda_k = \min_{S \subseteq \mathbb R^V} \max_{0 \neq f \in S} \mathcal R_G(f),$

where the minimum is over all k-dimensional subspaces $S$ .

[Hint: Have your subspace be the span of k functions with disjoint supports, where the support of a function $f : V \to \mathbb R$ is $\mathrm{supp}(f) = \{ x \in V : f(x) \neq 0 \}$ .]