Georgia Institute of Technology College of Sciences

Cheeger's fundamental inequality states that any edge-weighted graph has a vertex subset $S$ such that its expansion (a.k.a. conductance of $S$ or the sparsity of the cut $(S,\bar{S})$)is bounded as follows: \phi(S) = w(S,S') /w(S) \leq \sqrt{2 \lambda_2},where $w$ is the total edge weight of a subset or a cut and $\lambda_2$ is the second smallest eigenvalue of thenormalized Laplacian of the graph.We study natural generalizations of the sparsest cut in a graph: (i) a partition ofthe vertex set into $k$ parts that minimizes the sparsity of the partition (defined as the ratio of theweight of edges between parts to the total weight of edges incident to the smallest $k-1$ parts); (ii) a collection of $k$ disjoint subsets $S_1, \ldots, S_k$ that minimize $\max_{i \in [k]} \phi(S_i)$; (iii) a subset of size $O(1/k)$ of the graph with minimum expansion. Our main results are extensions of Cheeger's classical inequality to these problems via higher eigenvalues of the graph Laplacian.In particular, for the sparsest $k$-partition, we prove that the sparsity is at most $8\sqrt{\lambda_k} \log k$where $\lambda_k$ is the $k^{th}$ smallest eigenvalue of the normalized Laplacian matrix.For the $k$ sparse cuts problem we prove that there exist$ck$ disjoint subsets $S_1, \ldots, S_{(1 - \eps)k}$, such that \max_i \phi(S_i) \leq C \sqrt{\lambda_{k} \log k}where $C>0$ are suitable absolute constants; this leads to a similar bound for the small-set expansion problem, namely for any $k$, there is a subset $S$ whoseweight is at most a $\bigO(1/k)$ fraction of the total weight and $\phi(S) \le C \sqrt{\lambda_k \log k}$. The latter two results are the best possible in terms of the eigenvalues up to constant factors. Our results are derived via simple and efficient algorithms, and can themselves be viewed as generalizations of Cheeger's method.Based on joint work with Prasad Raghavendra, Prasad Tetali and Santosh Vempala.