Cutoff phenomena for random walks on random regular graphs (Q984454)

This paper is a study of random walks on random regular graphs. First, the authors give a sharp estimate on the mixing time of a lazy random walk on a random 3-regular graph, showing that with high probability this is approximately \(6 \log_2 n\), confirming a conjecture of Durrett. Furthermore, they show that the random walk exhibits a cut-off behaviour for any fixed \(d\), which is at least 3. Namely, the time \((d/(d-2)) \log_{d-1} n\) is the point where the random walk ``moves'' quickly from far from mixing to very close to mixing. Also, they show that the transition window has order \(\sqrt{\log n}\). The authors also consider non-backtracking random walks where they show that cutoff occurs at time \(\log_{d-1} n\) and the window has constant order. Random regular graphs with growing \(d\), namely \(d=n^{o(1)}\), are also investigated, where concentration of the mixing time on two integer values is shown.