You can see notes for this lecture here. In the next lecture, we will cover a different approach based on these notes.

# Category Archives: Notes

# Remarks on Lecture 3

Today we saw the connection between mixing times of random walks and the second eigenvalue of the normalized Laplacian. Recall that is an -vertex, weighted graph.

First, we introduced the lazy walk matrix,

which is related to the normalized Laplacian via,

In particular, if we arrange the eigenvalues of as , then

where is the th smallest eigenvalue of . Furthermore, the eigenfunctions of are given by , where is an eigenfunction of .

The eigenfunctions of are orthogonal with respect to the inner product

We will refer to this Hilbert space as . Recall that .

If we define the stationary distribution by

then .

Let be an -orthornormal system of eigenvectors for . Now fix an initial distribution and write,

Then we have,

In particular,

Let be the minimum stationary measure. A particularly strongly notion of mixing time is given by the following definition.

where the supremum is taken over all initial distributions . By time , the distribution is *pointwise* very close to the stationary distribution .

Let and . Using our preceding calculation, we have

Observe that , so if we now choose appropriately, then

yielding our main result:

One can also proof that (see the exercises). In general, we will be concerned with weaker notions of mixing. We’ll discuss those when they arise.

### Excersies

Prove that for any graph G.

# Remarks on Lecture 2

In this lecture, we generalized our setting to weighted graphs where is a positive weight function on edges. We also looked at the basic spectral theory of the *normalized Laplacian*, defined by

,

which operates on functions via

.

In particular, we associated with the normalized Rayleigh quotient,

,

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

.

We defined the *expansion* of a subset by

,

where is the characteristic function for .

Finally, we defined the *expansion of a graph* by

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

Theorem 1.For any weighted graph , we have,

where .

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

# Remarks on Lecture 1

Today we started studying the spectrum of the combinatorial Laplacian on a graph . This is the operator given by

We saw that has a spectrum of the form , and that the number of connected components in is precisely the multiplicity of .

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 , we define its *Rayleigh quotient* by

If is the path graph on n vertices, then as we argued today, we have .

- Prove that by showing that (a) there exists a map with and and (b) for any such map with , we have . We did this in class, but it will help to reconstruct the proof on your own.

- Try to prove that 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 thatwhere the minimum is over all k-dimensional subspaces .

[Hint: Have your subspace be the span of k functions with disjoint supports, where the support of a function is .]