# 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.