Go here to sign up: https://mailman1.u.washington.edu/mailman/admin/cse599i_sp12
We discussed combinatorial and spectral notions of graph expansion and sketched why a random d-regular graph is an expander for d large enough. Then I presented Margulis’ expander construction and the Gabber-Galil analysis. To end, we proved that expanders require logarithmic distortion to embed into any Euclidean space.
Here is a modified analysis of the Margulis expanders.
From this paper, we know that for an n-vertex planar graph with maximum degree , we have for every k, the eigenvalue bound
Open question: What about the eigenvalue gaps? I conjecture that the stronger bound holds for every k. I believe it is open even for k=2.
This homework is due in two weeks on Wednesday, April 18th. You make work in small groups of 2 or 3. You should reference any discussions with others, books, lecture notes, or other resources that you use in coming up with a solution.
[Reminder: The notation is the same as and is defined as the conjuniction of and .]
- Let be the adjacency matrix of a -regular graph . Prove that is bipartite if and only if has as an eigenvalue.
- Consider the two-dimensional grid graph . Let . Prove that
where refers to the second eigenvalue of the combinatorial Laplacian. (Prove this without using the Spielman-Teng theorem for planar graphs.) For the lower bound, it may help to remember that , where is the path on vertices.
- Let for some integer . Prove that if is the complete binary tree of height , we have
where again refers to the combinatorial Laplacian.
- Let be an arbitrary graph. Recall that
Let be the second eigenvalue of the combinatorial Laplacian on .
where both minimums are over non-constant functions.
- Let be a -regular graph and set , where is the adjacency matrix of . Let be defined as in the notes for lecture 3. Let be the eigenvalues of . Prove that
by evaluating in two different ways.
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
Let be an -orthornormal system of eigenvectors for . Now fix an initial distribution and write,
Then we have,
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.
Prove that for any graph G.