Abrupt equilibration on every family of transitive expanders
Let $(G_n)$ be connected vertex-transitive finite simple graphs with $|V(G_n)| \to \infty$ and all degrees at most a fixed $D$. Let $P_n$ be the lazy simple random walk on $G_n$, which stays put with probability $1/2$ and otherwise moves to a uniform neighbour, and assume that the spectral gaps of the $P_n$ are bounded below by a fixed $\gamma > 0$. Let $$t_n(\varepsilon) = \min\bigl\{t : \max_x \|P_n^t(x,\cdot) - \mathrm{Unif}(V(G_n))\|_{\mathrm{TV}} \le \varepsilon\bigr\}.$$ Lubetzky and Peres proved that the simple random walk on every Ramanujan graph exhibits cutoff. Lubetzky and Sly constructed cubic expanders without cutoff, so the transitivity assumption cannot simply be dropped. Salez showed that a sequence of expanders exhibits cutoff if and only if a varentropy condition holds.
Problem. Must $t_n(\varepsilon)/t_n(1-\varepsilon) \to 1$ for every $0 < \varepsilon < 1/2$?
Source: Peres (2004), ARCC workshop Sharp Thresholds for Mixing Times, Open Question 34; Levin and Peres (2017), Chapter 26, Question 5; Salez (2024), Conjecture 1.7.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- CO
- Keywords
- AIM Open Applied Problems, cutoff phenomenon, expander graphs, vertex-transitive graphs
References
@misc{goel2004,
author = {Goel, Sharad and Nachmias, Asaf and Ralph, Peter and Shah, Devavrat},
title = {{ARCC} workshop: sharp thresholds for mixing times},
howpublished = {Open problems from the workshop, American Institute of Mathematics, Palo Alto, December 20--23, 2004},
year = {2004},
url = {https://www.aimath.org/WWN/mixingtimes/mixingtimes.pdf},
note = {Scribed notes; Open Question 34, from the talk of Yuval Peres},
}
@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},
}
@article{salez2024,
author = {Salez, Justin},
title = {The varentropy criterion is sharp on expanders},
journal = {Ann. Henri Lebesgue},
volume = {7},
year = {2024},
pages = {239--250},
doi = {10.5802/ahl.199},
}
@article{lubetzky2016,
author = {Lubetzky, Eyal and Peres, Yuval},
title = {Cutoff on all {R}amanujan graphs},
journal = {Geom. Funct. Anal.},
volume = {26},
number = {4},
year = {2016},
pages = {1190--1216},
doi = {10.1007/s00039-016-0382-7},
eprint = {1507.04725},
archivePrefix = {arXiv},
}
@article{lubetzky2011,
author = {Lubetzky, Eyal and Sly, Allan},
title = {Explicit expanders with cutoff phenomena},
journal = {Electron. J. Probab.},
volume = {16},
year = {2011},
pages = {419--435},
doi = {10.1214/EJP.v16-869},
eprint = {1003.3515},
archivePrefix = {arXiv},
}
@misc{aim-transitive-expander-cutoff,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Abrupt equilibration on every family of transitive expanders}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/268-transitive-expander-cutoff.md},
note = {Entry 268 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-00484, "Abrupt equilibration on every family of transitive expanders", clopen.solutions.