Title : Higher Order Cheeger Inequalities 

Abstract : 

Cheeger's fundamental inequality says that any edge-weighted graph has a vertex subset whose weighted expansion (a.k.a. conductance) is bounded by twice the square root of the second smallest eigenvalue of the normalized Laplacian of the graph. This inequality and its algorithmic proof have a myriad of applications. 

We present a generalization: for any integer k less than n, there exist c.k disjoint subsets such that the expansion of each one is bounded by C\sqrt{\lambda_k \log k}, where \lambda_k is the k'th largest eigenvalue of the normalized Laplacian and c,C are absolute constants. Our proof is via a polynomial-time algorithm to find such subsets, using spectral projection and randomized rounding and can be seen as an extension of the Cheeger method. As a consequence, we get the same upper bound for the small-set expansion problem, namely for any k, there is a subset whose weight is an O(1/k) fraction of the total weight and its expansion is bounded by C\sqrt{\lambda_k \log k}. Both results are the best possible up to constant factors. 

The underlying algorithmic problem, namely finding k subsets such that the maximum expansion is minimized, besides extending sparse cuts to more than one subset, appears to be a natural clustering problem in its own right.

Joint work with Santosh Vempala and a couple of Prasads.