Cutoff conjecture for simple random walk on vertex-transitive expander graphs
Cutoff conjecture for simple random walk on vertex-transitive expander graphs
Let 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 -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
Sign in to submit a solution.
No solutions have been posted yet.