@article{EJP869,
author = {Eyal Lubetzky and Allan Sly},
title = {Explicit Expanders with Cutoff Phenomena},
journal = {Electron. J. Probab.},
fjournal = {Electronic Journal of Probability},
volume = {16},
year = {2011},
keywords = {Cutoff phenomenon; Random walks; Expander graphs; Explicit constructions},
abstract = {The cutoff phenomenon describes a sharp transition in the convergence of an ergodic finite Markov chain to equilibrium. Of particular interest is understanding this convergence for the simple random walk on a bounded-degree expander graph. The first example of a family of bounded-degree graphs where the random walk exhibits cutoff in total-variation was provided only very recently, when the authors showed this for a typical random regular graph. However, no example was known for an explicit (deterministic) family of expanders with this phenomenon. Here we construct a family of cubic expanders where the random walk from a worst case initial position exhibits total-variation cutoff. Variants of this construction give cubic expanders without cutoff, as well as cubic graphs with cutoff at any prescribed time-point.},
pages = {no. 15, 419-435},
issn = {1083-6489},
doi = {10.1214/EJP.v16-869},
url = {http://ejp.ejpecp.org/article/view/869}}