Go here to sign up: https://mailman1.u.washington.edu/mailman/admin/cse599i_sp12

# Monthly Archives: April 2012

# Lecture 7-8

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.

# Lecture 6

Here are the slides, and here’s a proof of the crossing number inequality.

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.

# Lecture 5

# Homework #1

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

### Problems

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

Prove that,

and

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.

# Remarks on Lecture 4

You can see notes for this lecture here. In the next lecture, we will cover a different approach based on these 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.