Spectral graph theory studies connections between combinatorial properties of graphs and the eigenvalues of matrices associated to the graph, such as the adjacency matrix and the Laplacian matrix.

Spectral graph theory has applications to the design and analysis of approximation algorithms for graph partitioning problems, to the study of random walks in graph, and to the construction of expander graphs. It also reveals connections between the above topics, and provides, for example, a way to use random walks to approximately solve graph partitioning problems.

In this series of lectures we will introduce the basics of spectral graph theory, we will prove the discrete Cheeger inequalities, and see them as (i) a way to approximate the sparsest cut problem, (ii) an approach to bound the mixing time of random walks, and (iii) a way to certify expansion in graphs. We will then consider various generalizations of this result, such as higher-order Cheeger inequalities, a Cheeger-like inequality for the largest eigenvalue of the Laplacian, and the expander mixing lemma and its inverse. Each of these more advanced results will also be interpreted as the analysis of an approximation algorithm for a graph partitioning problem.

The second session of this talk will take place on Tuesday, August 26 from 2:00 pm – 3:00 pm; the third session of this talk will take place on Wednesday, August 27 from 10:00 am – 11:00 am.

Related Links

Lecture Notes on Expansion, Sparsest Cut, and Spectral Graph Theory
http://www.eecs.berkeley.edu/~luca/books/expanders.pdf