Multi-way dual Cheeger constants and spectral bounds of graphs (Q471683): Difference between revisions

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.