Speaker: Lap Chi Lau,
University of Waterloo
Title: Improved Cheeger's inequalities
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.