A diameter bound for diffusion to uniform equilibrium
Let $G$ be a connected finite vertex-transitive simple graph with at least two vertices, degree $d$ and diameter $D$, and let $P = \tfrac12 I + \tfrac{1}{2d} A_G$ be the lazy simple random walk on $G$, where $A_G$ is the adjacency matrix. Let $t_{\mathrm{mix}}$ be the smallest integer $t$ with $\max_x \|P^t(x,\cdot) - \mathrm{Unif}(V(G))\|_{\mathrm{TV}} \le 1/4$. Levin and Peres proved that the relaxation time of the simple random walk on $G$ is at most $2 d D^2$.
Problem. Is there a universal constant $C$ with $t_{\mathrm{mix}} \le C d D^2$ for every such $G$?
Source: Levin and Peres (2017), Chapter 26, Question 8.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, mixing times, random walks on graphs, vertex-transitive graphs
References
@book{levin2017,
author = {Levin, David A. and Peres, Yuval},
title = {Markov Chains and Mixing Times},
edition = {Second},
note = {With contributions by Elizabeth L. Wilmer},
publisher = {American Mathematical Society},
address = {Providence, RI},
year = {2017},
doi = {10.1090/mbk/107},
}
@misc{aim-transitive-mixing-diameter,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{A diameter bound for diffusion to uniform equilibrium}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/271-transitive-mixing-diameter.md},
note = {Entry 271 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00485, "A diameter bound for diffusion to uniform equilibrium", clopen.solutions.