Rutgers Discrete Mathematics Seminar

Title: Random Walks on the Random Graph

Speaker: Eyal Lubetzky, NYU

Date: Monday, April 20, 2015 11:00 am

Location: CoRE Bldg, Room 431, Rutgers University, Busch Campus, Piscataway, NJ


We study random walks on the giant component of the ErdH{o}s-R'enyi 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.