Random walks on the random graph
Authors:
- Nathanael BerestyckiNBNathanael Berestycki
- Eyal LubetzkyELEyal Lubetzky
- Yuval PeresYPYuval Peres
- Allan SlyASAllan Sly
Preprint
Abstract
We study random walks on the giant component of the Erd\H{o}s-R\'enyi random graph ${\cal 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 {\bf d})^{-1}\log n \pm (\log n)^{1/2+o(1)}$, where $\nu$ and ${\bf d}$ are the speed of random walk and dimension of harmonic measure on a ${\rm 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.
Keywords
All Related Versions
This publication has 15 references indexed in Scilit:
- The mixing time of the giant component of a random graphRandom Structures & Algorithms, 2014
- Anatomy of the giant component: The strictly supercritical regimeEuropean Journal of Combinatorics, 2014
- Anatomy of a young giant component in the random graphRandom Structures & Algorithms, 2010
- Critical random graphs: Diameter and mixing timeThe Annals of Probability, 2008
- The evolution of the mixing rate of a simple random walk on the giant component of a random graphRandom Structures & Algorithms, 2008
- Faster Mixing and Small BottlenecksProbability Theory and Related Fields, 2006
- Biased random walks on Galton–Watson treesProbability Theory and Related Fields, 1996
- Functional Limit Theorems for the Simple Random Walk on a Supercritical Galton-Watson Tree1996
- Ergodic theory on Galton—Watson trees: speed of random walk and dimension of harmonic measureErgodic Theory and Dynamical Systems, 1995
- Component behavior near the critical point of the random graph processRandom Structures & Algorithms, 1990