  A basic fact in spectral graph theory is that the number of connected
components in an undirected graph is equal to the multiplicity of the
eigenvalue zero in the Laplacian matrix of the graph. In particular, the graph
is disconnected if and only if there are at least two eigenvalues equal to
zero. Cheeger's inequality and its variants provide an approximate version of
the latter fact; they state that a graph has a sparse cut if and only if there
are at least two eigenvalues that are close to zero.
  It has been conjectured that an analogous characterization holds for higher
multiplicities, i.e., there are $k$ eigenvalues close to zero if and only if
the vertex set can be partitioned into $k$ subsets, each defining a sparse cut.
We resolve this conjecture. Our result provides a theoretical justification for
clustering algorithms that use the bottom $k$ eigenvectors to embed the
vertices into $\mathbb R^k$, and then apply geometric considerations to the
embedding.
  We also show that these techniques yield a nearly optimal tradeoff between
the expansion of sets of size $\approx n/k$, and the $k$th smallest eigenvalue
of the normalized Laplacian matrix, denoted $\lambda_k$. In particular, we show
that in every graph there is a set of size at most $2n/k$ which has expansion
at most $O(\sqrt{\lambda_k \log k})$. This bound is tight, up to constant
factors, for the "noisy hypercube" graphs.
