RANDOM WALKS ON THE RANDOM GRAPH

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 log2n. We prove that starting from a uniform vertex (equivalently, from a fixed vertex conditioned to belong to the giant) both accelerates mixing to O(logn) and concentrates it (the cutoff phenomenon occurs): the typical mixing is at (νd)−1logn±(logn)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 nonbacktracking random walk.