Multi-way dual Cheeger constants and spectral bounds of graphs
From MaRDI portal
(Redirected from Publication:471683)
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 878889 (Why is no real title available?)
- scientific article; zbMATH DE number 3337135 (Why is no real title available?)
- scientific article; zbMATH DE number 964896 (Why is no real title available?)
- A characterization of the smallest eigenvalue of a graph
- 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.)
- Approximate counting, uniform generation and rapidly mixing Markov chains
- Bipartite and neighborhood graphs and the spectrum of the normalized graph Laplace operator
- Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
- Cayley graph expanders and groups of finite width.
- Criteria of spectral gap for Markov operators
- Difference Equations, Isoperimetric Inequality and Transience of Certain Random Walks
- Discrete groups, expanding graphs and invariant measures. Appendix by Jonathan D. Rogawski
- Eigenvalues and expanders
- Eigenvalues of Graphs and Sobolev Inequalities
- Explicit Concentrators from Generalized N-Gons
- Extending Lipschitz functions via random metric partitions
- Geometric bounds for eigenvalues of Markov chains
- Higher eigenvalues and isoperimetric inequalities on Riemannian manifolds and graphs
- Hypercontra ctive semigroups and two dimensional self-coupled Bose fields
- Improved Cheeger's inequality, analysis of spectral partitioning algorithms through higher order spectral gap
- Interlacing for weighted graphs using the normalized Laplacian
- Interlacing inequalities for eigenvalues of discrete Laplace operators
- Isoperimetric numbers of graphs
- Max cut and the smallest eigenvalue
- Metric uniformization and spectral bounds for graphs
- Ollivier-Ricci curvature and the spectrum of the normalized graph Laplace operator
- On eigenfunctions of Markov processes on trees
- On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
- Riemannian geometry
- The dual Cheeger constant and spectra of infinite graphs
- Upper bounds for eigenvalues of the discrete and continuous Laplace operators
- \(\lambda_ 1\), isoperimetric inequalities for graphs, and superconcentrators
Cited in
(20)- Curvature and higher order Buser inequalities for the graph connection Laplacian
- Eigenvalue ratios of non-negatively curved graphs
- scientific article; zbMATH DE number 5016633 (Why is no real title available?)
- On nodal domains and higher-order Cheeger inequalities of finite reversible Markov processes
- Cheeger estimates of Dirichlet-to-Neumann operators on infinite subgraphs of graphs
- Computing the Weighted Geometric Mean of Two Large-Scale Matrices and Its Inverse Times a Vector
- Bipartite communities via spectral partitioning
- Cheeger constants, structural balance, and spectral clustering analysis for signed graphs
- Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians
- A note on Cheeger inequalities for piecewise flat surfaces
- On a Cheeger type inequality in Cayley graphs of finite groups
- The dual Cheeger constant and spectra of infinite graphs
- Cheeger inequalities for the discrete magnetic Laplacian
- Doubling constants and spectral theory on graphs
- Some consequences of an inequality on the spectral multiplicity of graphs
- Generalizations of Szőkefalvi Nagy and Chebyshev inequalities with applications in spectral graph theory
- Mean isoperimetry with control on outliers: exact and approximation algorithms
- Spectral distances on graphs
- Frustration index and Cheeger inequalities for discrete and continuous magnetic Laplacians
- Dirichlet \(p\)-Laplacian eigenvalues and Cheeger constants on symmetric graphs
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)
