Spectral Graph Theory Lecture 6 Conductance, the Normalized Laplacian, and Cheeger’s Inequality

These notes are not necessarily an accurate representation of what happened in class. The notes written before class say what I think I should say. I sometimes edit the notes after class to make them way what I wish I had said. There may be small mistakes, so I recommend that you check any mathematically precise statement before using it in your own work. These notes were last revised on September 21, 2015. 6.1 Overview As the title suggests, in this lecture I will introduce conductance, a measure of the quality of a cut, and the normalized Laplacian matrix of a graph. I will then prove Cheeger’s inequality, which relates the second-smallest eigenvalue of the normalized Laplacian to the conductance of a graph. Cheeger [Che70] first proved his famous inequality for manifolds. Many discrete versions of Cheeger’s inequality were proved in the late 80’s [SJ89, LS88, AM85, Alo86, Dod84, Var85]. Some of these consider the walk matrix (which we will see in a week or two) instead of the normalized Laplacian, and some consider the isoperimetic ratio instead of conductance. The proof that I present today follows an approach developed by Luca Trevisan [Tre11]. 6.2 Conductance Back in Lecture 2, we related to isoperimetric ratio of a subset of the vertices to the second eigenvalue of the Laplacian. We proved that for every S ⊂ V θ(S) ≥ λ2(1 − s), where s = |S | / |V | and θ(S) de