Random walks on random graphs

03/17/2016 - 16:30
03/17/2016 - 17:30
Eyal Lubetzky
McGill, Burnside Hall 1205

 We will discuss the behavior of the random walk on two random graph models: on one hand the random regular graph with fixed degree, and on the other hand the giant component of the supercritical ErdÅ‘s-Renyi random graph with constant average degree. In the former case it is known that the walk mixes in logarithmic time and exhibits the cutoff phenomenon. In the latter case, while starting from the worst initial vertex---as shown by Fountoulakis-Reed and independently by Benjamini-Kozma-Wormald---both delays mixing and precludes cutoff, it turns out that starting from a fixed vertex induces the rapid mixing behavior of the regular case. For general locally-tree-like random graphs, we express the mixing time in terms of the speed and dimension of harmonic measure of random walk on the corresponding Galton-Watson tree.

Based on joint works with N. Berestycki, Y. Peres, and A. Sly

Last edited by on Thu, 03/10/2016 - 16:03