Multi-way dual Cheeger constants and spectral bounds of graphs
From MaRDI portal
Publication:471683
DOI10.1016/J.AIM.2014.09.023zbMATH Open1309.05122arXiv1401.3147OpenAlexW2066093465MaRDI QIDQ471683FDOQ471683
Publication date: 17 November 2014
Published in: Advances in Mathematics (Search for Journal in Brave)
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.
Full work available at URL: https://arxiv.org/abs/1401.3147
Recommendations
spectral clusteringessential spectrumMarkov operatorsCheeger constantshigher-order dual Cheeger inequalities
Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Discrete-time Markov processes on general state spaces (60J05) Spectral problems; spectral geometry; scattering theory on manifolds (58J50)
Cites Work
- Title not available (Why is that?)
- Eigenvalues and expanders
- Extending Lipschitz functions via random metric partitions
- Analyse harmonique non-commutative sur certains espaces homogènes. Etude de certaines intégrales singulières. (Non-commutative harmonic analysis on certain homogeneous spaces. Study of certain singular integrals.)
- Title not available (Why is that?)
- Riemannian geometry
- Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
- Isoperimetric numbers of graphs
- Geometric bounds for eigenvalues of Markov chains
- A characterization of the smallest eigenvalue of a graph
- Approximate counting, uniform generation and rapidly mixing Markov chains
- The dual Cheeger constant and spectra of infinite graphs
- Explicit Concentrators from Generalized N-Gons
- Max Cut and the Smallest Eigenvalue
- On eigenfunctions of Markov processes on trees
- Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
- Criteria of spectral gap for Markov operators
- Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
- Improved Cheeger's inequality
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
- Higher eigenvalues and isoperimetric inequalities on Riemannian manifolds and graphs
- Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
- Eigenvalues of Graphs and Sobolev Inequalities
- Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator
- Title not available (Why is that?)
- On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
- Cayley graph expanders and groups of finite width.
- Upper bounds for eigenvalues of the discrete and continuous Laplace operators
- Interlacing inequalities for eigenvalues of discrete Laplace operators
- Hypercontra ctive semigroups and two dimensional self-coupled Bose fields
- Interlacing for weighted graphs using the normalized Laplacian
- Multi-way spectral partitioning and higher-order cheeger inequalities
- Metric uniformization and spectral bounds for graphs
Cited In (18)
- Title not available (Why is that?)
- Generalizations of Szőkefalvi Nagy and Chebyshev inequalities with applications in spectral graph theory
- Computing the Weighted Geometric Mean of Two Large-Scale Matrices and Its Inverse Times a Vector
- Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians
- Dirichlet \(p\)-Laplacian eigenvalues and Cheeger constants on symmetric graphs
- A Note on Cheeger Inequalities for Piecewise Flat Surfaces
- Bipartite communities via spectral partitioning
- On a Cheeger type inequality in Cayley graphs of finite groups
- Spectral distances on graphs
- Mean isoperimetry with control on outliers: exact and approximation algorithms
- Some consequences of an inequality on the spectral multiplicity of graphs
- Cheeger estimates of Dirichlet-to-Neumann operators on infinite subgraphs of graphs
- Eigenvalue Ratios of Non-Negatively Curved Graphs
- Cheeger inequalities for the discrete magnetic Laplacian
- Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
- Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians
- Doubling constants and spectral theory on graphs
- Curvature and Higher Order Buser Inequalities for the Graph Connection Laplacian
This page was built for publication: Multi-way dual Cheeger constants and spectral bounds of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q471683)
