Multi-way dual Cheeger constants and spectral bounds of graphs

Liu, Shiping

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.

Citation

Liu, S. (2015). Multi-way dual Cheeger constants and spectral bounds of graphs. Advances in Mathematics, 268, 306-338. https://doi.org/10.1016/j.aim.2014.09.023

• Journal Article Type: Article
• Acceptance Date: Sep 29, 2014
• Online Publication Date: Oct 10, 2014
• Publication Date: Jan 2, 2015
• Deposit Date: Aug 14, 2014
• Publicly Available Date: Oct 13, 2014
• Journal: Advances in Mathematics
• Print ISSN: 0001-8708
• Publisher: Elsevier
• Peer Reviewed: Peer Reviewed
• Volume: 268
• Pages: 306-338
• DOI: https://doi.org/10.1016/j.aim.2014.09.023
• Keywords: Cheeger constants, Higher-order dual Cheeger inequalities, Spectral clustering, Markov operators, Essential spectrum.
• Public URL: https://durham-repository.worktribe.com/output/1422296