Multi-way dual Cheeger constants and spectral bounds of graphs
arXiv:1401.3147 · doi:10.1016/j.aim.2014.09.023
Abstract
We introduce a set of multi-way dual Cheeger constants and prove universal higher-order dual Cheeger inequalities for eigenvalues of normalized Laplace operators on weighted finite graphs. Our proof proposes a new spectral clustering phenomenon deduced from metrics on real projective spaces. We further extend those results to a general reversible Markov operator and find applications in characterizing its essential spectrum.
30 pages, 1 figure, revised; Theorem 6.4 added. Comments are welcome