Our agenda for the next few weeks looks something like this:
- The discrete Cheeger inequality
- The connection between 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
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
- 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.
This is the course web site for CSE 599S: Algorithmic Spectral Graph Theory. This is where notes, homeworks, and video will be posted.
The class will be held every Monday and Wednesday, from 3-4:20pm in CSE 305.