Sharp bounds on eigenvalues via spectral embedding based on signless Laplacians

DOI10.1016/J.JFA.2022.109799zbMATH Open1506.05129arXiv2111.08777OpenAlexW4226378490MaRDI QIDQ2112759FDOQ2112759

Authors: Zhi-Feng Wei 

Publication date: 11 January 2023

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

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].

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

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

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)

Cites Work

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

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)