Cutoff conjecture for simple random walk on vertex-transitive expander graphs

From papers

Let (Gn)(G_n) be any family of finite vertex-transitive expander graphs, and let the simple random walk (SRW) be the walk that at each step moves uniformly to a neighboring vertex. Vertex-transitive expander cutoff conjecture. The SRW on any family of vertex-transitive expander graphs exhibits cutoff. The paper has established cutoff for simple and non-backtracking random walks on almost every dd-regular graph in its stated degree range, but notes that arbitrary expander families may have asymmetric counterexamples and presents this assertion as plausible; its general validity remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Eyal Lubetzky and Allan Sly, “Cutoff phenomena for random walks on random regular graphs”, arXiv:0812.0060 (2009).

Solutions 0

No solutions have been posted yet.