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.

Synopsis:

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.