Abstract. We study random walks on the giant component of the Erdős-Rényi random graph G(n, p) where p = λ/n for λ > 1 fixed. The mixing time from a worst starting point was shown by Fountoulakis and Reed, and independently by Benjamini, Kozma and Wormald, to have order log 2 n. We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to O(log n) and concentrates it (the cutoff phenomenon occurs): the typical mixing is at (νd) −1 log n ± (log n) 1/2+o (1) , where ν and d are the speed of random walk and dimension of harmonic measure on a Poisson(λ)-Galton-Watson tree. Analogous results are given for graphs with prescribed degree sequences, where cutoff is shown both for the simple and for the non-backtracking random walk.
In REF , Berestycki, Lubetzky, Peres and Sly establish the cutoff phenomenon on the Erdős-Renyi model and on the more general configuration model, for both the simple and non-backtracking random walks.
Random walks on the random graph
arXiv: Probability
Mathematics