Abstract
The Cheeger inequality in graphs relates the second smallest eigenvalue of the Laplacian of the graph to the conductance of the graph. It has applications to approximation algorithms, as an analysis of the "sweep" partitioning algorithm; to the construction of expander graphs; and to the analysis of random walks in graphs. We describe a generalization that relatex the k-th smallest eigenvalue of the Laplacian to the "order-k" conductance of a graph, and discuss its connection to the analysis of spectral partitioning algorithms. We also show a tighter Cheeger inequality for graphs of bounded "threshold rank," giving an improved analysis of the sweep algorithm in such graphs.