A Higher-Order Cheeger's Inequality

Details A Higher-Order Cheeger's Inequality A Higher-Order Cheeger's Inequality

2011-07-13

arxiv.org/abs/1107.2686v2

Computer Science

Data Structures and Algorithms

This paper has been withdrawn by the author since a simpler and more general result is recently posted at http://arxiv.org/abs

Scientific paper

A basic fact in algebraic graph theory is that the number of connected components in an undirected graph is equal to the multiplicity of the eigenvalue 1 in the normalized adjacency matrix of the graph. In particular, the graph is disconnected if and only if there are at least two eigenvalues equal to 1. Cheeger's inequality provides an "approximate" version of the latter fact, and it states that a graph has a sparse cut (it is "almost disconnected") if and only if there are at least two eigenvalues that are close to one. It has been conjectured that an analogous characterization holds for higher multiplicities, that is there are $k$ eigenvalues close to 1 if and only if the vertex set can be partitioned into $k$ subsets, each defining a sparse cut. In this paper we resolve this conjecture. Our result provides a theoretical justification for clustering algorithms that use the top $k$ eigenvector to embed the vertices into $\R^k$, and then apply geometric considerations to the embedding.

Affiliated with

Also associated with

No associations

Rating

A Higher-Order Cheeger's Inequality does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Higher-Order Cheeger's Inequality, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Higher-Order Cheeger's Inequality will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-224509