MATH 261
Topics in Probabilistic Combinatorics and Algorithms
Spring, 2008

• Spectral Graph Theory,
  by F. Chung, CBMS Lecture Notes, AMS Publications, 1992.
  The first four chapters are available on-line.
• Reversible Markov Chains and Random Walks on Graphs, (Monograph in preparation)
  by D. Aldous and J. Fill.
  http://www.stat.berkeley.edu/users/aldous/RWG/book.html

• Lecture 1: An overview. What is the shape of a graph? Connections to other areas of mathematics and applications.
• Lecture 2: Adjacency matrix, the combinatorial Laplacian, the normalized Laplacian. A short proof of Matrix-tree theorem.
• Lecture 3: Basic properties of the (normalized) Laplacian. Connectivity and the multiplicity of the zero eigenvalue.
• Lecture 4: Ten equivalent definitions of eigenvalues of the Laplacian
• Lecture 5: Basic properties about the spectral gap λ. Random walks on graphs.
• Lecture 6: Three measures for convergence of random walks.
• Lecture 7: Two applications of spectral methods: Approximating the volume of polypopes and counting 3-term Arithmetic progressions.
• Lecture 8: Isoperimetic problems, the Cheeger constant and the Cheeger inequality
• Lecture 9: Dirichlet eigenvalues and a local Cheeger inequality
• Lecture 10: Network flow and a vertex Cheeger inequality
• Lecture 11: A PageRank Cheeger inequality and local partition algorithms
• Lecture 12: More on Cheeger inequalities using random walks and pageranks.
• Lecture 13: Diameters and eigenvalues
• Lecture 14: Expanders with applications
• Lecture 15: Discrepancy inequalities