The maximum relaxation time of a random walk

DOI10.1016/J.AAM.2018.07.002MaRDI QIDQ1795486zbMATH OpenOpenAlexWikidataFDO

Authors Sinan Aksoy, Michael Tait, Josh Tobin, Fan Chung

Publication date 16 October 2018

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

spectral graph theoryMarkov chainsextremal graph theoryrandom walks on graphs

Mathematics Subject Classification ID

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

Abstract: We show the minimum spectral gap of the normalized Laplacian over all simple, connected graphs on $n$ vertices is $(1+o(1))frac54n^3$. This minimum is achieved asymptotically by a double kite graph. Consequently, this leads to sharp upper bounds for the maximum relaxation time of a random walk, settling a conjecture of Aldous and Fill. We also improve an eigenvalue-diameter inequality by giving a new lower bound for the spectral gap of the normalized Laplacian. This eigenvalue lower bound is asymptotically best possible.

Recommendations

• Regular graphs with minimum spectral gap
• Quartic graphs with minimum spectral gap
• The simple random walk and max-degree walk on a directed graph
• Spectral gap of the largest eigenvalue of the normalized graph Laplacian
• On the spectral gap and the diameter of Cayley graphs

Cites work

• scientific article; zbMATH DE number 964896 (Why is no real title available?)
• A tight upper bound on the cover time for random walks on graphs
• Bounds for eigenvalues of certain stochastic matrices
• Collecting coupons on trees, and the cover time of random walks
• Collisions Among Random Walks on a Graph
• Extremizing algebraic connectivity subject to graph theoretic constraints
• Graphs of given order and size and minimum algebraic connectivity
• Graphs with small spectral gap
• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Maximum hitting time for random walks on graphs
• Minimizing Effective Resistance of a Graph
• On the Spectral Radius of Complementary Acyclic Matrices of Zeros and Ones
• Some Extremal Markov Chains
• The Editor's Corner: The White Screen Problem

Cited in

(6)

• Aldous's spectral gap conjecture for normal sets
• Regular graphs with minimum spectral gap
• Graphs of degree at least \({3}\) with minimum algebraic connectivity
• Quartic graphs with minimum spectral gap
• Computing Kemeny's constant for a barbell graph
• Minimum algebraic connectivity and maximum diameter: Aldous-Fill and Guiduli-Mohar conjectures

This page was built for publication: The maximum relaxation time of a random walk

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