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.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math