Random walks on the random graph

Abstract

We study random walks on the giant component of the Erdős-Rényi random graph $\mathcal{G}(n,p)$ where $p=\lambda /n$ for $\lambda >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 $(\nu \mathbf{d}{)}^{-1}\log n\pm (\log n{)}^{1/2+o(1)}$, where $\nu$ and $\mathbf{d}$ are the speed of random walk and dimension of harmonic measure on a $\mathrm{Poisson}(\lambda )$-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.

29 pages, 3 figures

Cited by in corpus (1)

• Queues on a dynamically evolving graph