The maximum relaxation time of a random walk on regular graphs

Abstract

We establish sharp quadratic bounds on the relaxation time of simple random walk on connected regular graphs, with leading constants $3/(2{\pi }^2)$ and $1/{\pi }^2$ for even and odd orders, respectively. This resolves a longstanding conjecture known as Aldous--Fill spectral gap conjecture (2002). We also prove uniqueness and stability theorems for the corresponding cubic and quartic chains, and settle the quartic uniqueness conjecture posed by Abdi, Ghorbani, and Imrich (2021) and by Abdi and Ghorbani (2023). We establish sharp bounds on algebraic connectivity under minimum-degree and regularity constraints and prove the conjectured chain structure of the minimisers, identifying their repeating blocks. This resolves a longstanding conjecture of Guiduli and Mohar (1996) and a structural conjecture of Abdi and Ghorbani (2024). Our quantitative stability theorem shows that nearly minimum algebraic connectivity forces nearly maximum diameter, proving their diameter conjecture. We further obtain sharp relaxation-time bounds in terms of edge-connectivity. For nonregular graphs, we establish sharp bounds for the gap between maximum degree and adjacency spectral radius, confirming a conjecture of Liu (2024). As applications, we prove the sharp bounds on hitting and commute times conjectured by Aldous and Fill (2002) for regular graphs.

Substantially expanded version