Tutte Colloquium - Lap Chi Lau

Title: Improved Cheeger's inequalities

Abstract: Cheeger's inequality is a fundamental result in spectral graph theory relating the second eigenvalue to graph expansion.  We present two generalizations of Cheeger's inequality.  The first generalization
uses more spectral information (the second eigenvalue and the k-th
eigenvalue) to give an improved bound on the graph expansion.  The second generalization uses more combinatorial information (the edge expansion and the vertex expansion) to give an improved bound on the second eigenvalue. We discuss how these results provide better theoretical explanations of the empirical success of spectral partitioning algorithms.  We also mention some similar results for the analysis of random walks.