Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians

DOI10.1016/J.JFA.2022.109799MaRDI QIDQ2112759zbMATH OpenOpenAlexFDO

Authors Zhi-Feng Wei

Publication date 11 January 2023

Published in Journal of Functional Analysis (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2111.08777

zbMATH Keywords

return probabilitysignless Laplacianspectral embeddingspectral gap

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10) Random walks on graphs (05C81)

Abstract: Using spectral embedding based on the signless Laplacian, we obtain bounds on the spectrum of transition matrices on graphs. As a consequence, we bound return probabilities and the uniform mixing time of simple random walk on graphs. In addition, spectral embedding is used in this article to bound the spectrum of graph adjacency matrices. Our method is adapted from [Lyons and Oveis Gharan, 2017].

Recommendations

• Sharp bounds on random walk eigenvalues via spectral embedding
• Spectral graph theory via higher order eigenvalues and applications to the analysis of random walks
• Two sharp upper bounds for the signless Laplacian spectral radius of graphs
• Bounds on signless Laplacian eigenvalues of Hamiltonian graphs
• Graph Embeddings and Laplacian Eigenvalues

Cites work

• A Survey on Spectra of infinite Graphs
• A characterization of the smallest eigenvalue of a graph
• An elementary proof of the local central limit theorem
• Bipartite Subgraphs and the Smallest Eigenvalue
• Bounds for eigenvalues of certain stochastic matrices
• Counting Walks and Graph Homomorphisms via Markov Chains and Importance Sampling
• Geometric bounds for eigenvalues of Markov chains
• Mathematical aspects of mixing times in Markov chains.
• Max cut and the smallest eigenvalue
• Multi-way dual Cheeger constants and spectral bounds of graphs
• On the Convergence of Reversible Markov Chains
• On the diameter of a graph
• Probability on trees and networks
• Random walks on graphs: new bounds on hitting, meeting, coalescing and returning
• Sharp bounds on random walk eigenvalues via spectral embedding
• Spectra of graphs
• Spectral gap and convergence rate for discrete-time Markov chains
• Towards a spectral theory of graphs based on the signless Laplacian, III
• Towards a spectral theory of graphs based on the signless Laplacian. I
• Towards a spectral theory of graphs based on the signless Laplacian. II.

Cited in

(4)

• Graph Embeddings and Laplacian Eigenvalues
• Sharp bounds on random walk eigenvalues via spectral embedding
• New bounds for the spread of the signless Laplacian spectrum
• Majorization bounds for signless Laplacian eigenvalues

This page was built for publication: Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2112759)