The maximum relaxation time of a random walk on regular graphs
We establish sharp quadratic bounds on the relaxation time of simple random walk on connected regular graphs, with leading constants $3/(2π^2)$ and $1/π^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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2609.06818
curl -X POST /api/v1/records/arxiv/2609.06818/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.06818/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'