ABSTRACT:
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) = \frac{w(S, \bar{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 the
normalized Laplacian of the graph.
I will talk about some natural generalizations of the sparsest cut in a graph:
1. a partition of the vertex set into k parts that minimizes the sparsity of the partition (defined as the ratio of
the weight of edges between parts to the total weight of edges incident to the smallest k-1 parts);
2. a partition of the vertex set into k parts S_1, S_2, ... , S_k that minimize \max_{i \in [k]} \phi(S_i);
3. a subset of size O(1/k) of the graph with minimum expansion.
I will present some extensions of Cheeger's classical inequality to these problems via higher eigenvalues of the
graph Laplacian and some approximation-algorithms for them. 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, ..., S_{(1-z)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
whose weight is at most a O(1/k) fraction of the total weight and \phi(S) \leq 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 works with Prasad Raghavendra, Prasad Tetali and Santosh Vempala.