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.