Graduate Student / Postdoc Seminar
Random Walks on the Random Graph
Speaker: Eyal Lubetzky
Location: Warren Weaver Hall 1302
Date: Friday, April 24, 2015, 1 p.m.
We study random walks on the giant component of the Erdős-Rényi random graph \(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).
Joint work with N. Berestycki, Y. Peres and A. Sly.