Multi-way dual Cheeger constants and spectral bounds of graphs (Q471683): Difference between revisions
From MaRDI portal
Revision as of 06:55, 9 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Multi-way dual Cheeger constants and spectral bounds of graphs |
scientific article |
Statements
Multi-way dual Cheeger constants and spectral bounds of graphs (English)
0 references
17 November 2014
0 references
In the article under review, so-called multi-way dual Cheeger constants are introduced. Similar to the Cheeger inequality for the smallest non-zero eigenvalue of the normalized Laplace operator of a connected finite graph, the author proves higher order dual Cheeger inequalities for these multi-way dual Cheeger constants and the corresponding eigenvalues of the normalized Laplace operator of a weighted finite graph sorted by increasing order. The inequalities are useful for the second half of the spectrum with the larger eigenvalues. The author proves relations of these multi-way dual Cheeger constants to the respective multi-way Cheeger constants and equivalences and implications for special cases about connected components of the graph and if the graph is bipartite. One section is devoted to the multi-way dual Cheeger constants for trees and cycles and the comparison with the eigenvalues of the normalized Laplace operator. In the last section the notion of multi-way dual Cheeger constants is extended to characterize the essential spectrum of reversible Markov operators and similar inequalities in this case.
0 references
Cheeger constants
0 references
higher-order dual Cheeger inequalities
0 references
spectral clustering
0 references
Markov operators
0 references
essential spectrum
0 references
0 references
0 references
0 references
0 references