The maximum relaxation time of a random walk

DOI10.1016/J.AAM.2018.07.002zbMATH Open1397.05096arXiv1804.05500OpenAlexW2797354362WikidataQ129492606 ScholiaQ129492606MaRDI QIDQ1795486FDOQ1795486

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)

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• On the Spectral Radius of Complementary Acyclic Matrices of Zeros and Ones
• Maximum hitting time for random walks on graphs
• A tight upper bound on the cover time for random walks on graphs
• Extremizing algebraic connectivity subject to graph theoretic constraints
• Graphs of given order and size and minimum algebraic connectivity
• Collisions Among Random Walks on a Graph
• Minimizing Effective Resistance of a Graph
• Bounds for eigenvalues of certain stochastic matrices
• 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.
• Some Extremal Markov Chains
• Collecting coupons on trees, and the cover time of random walks
• 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
• Minimum algebraic connectivity and maximum diameter: Aldous-Fill and Guiduli-Mohar conjectures
• Computing Kemeny's constant for a barbell graph

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)