Printable PDF
Department of Mathematics,
University of California San Diego

****************************

Math 295 - Mathematics Colloquium

Eyal Lubetzky

Microsoft Research

Random regular graphs: from random walks to geometry and back.

Abstract:

The class of random regular graphs has been the focus of extensive study highlighting its excellent expansion properties. For instance, it is well known that almost every regular graph of fixed degree is essentially Ramanujan, and understanding this class of graphs sheds light on the general behavior of expanders. In this talk we will present several recent results on random regular graphs, focusing on the interplay between the spectrum, geometry and behavior of the simple random walk in these graphs. We will first discuss the relation between spectral properties and the abrupt convergence of the random walk to equilibrium, derived from precise asymptotics of the number of paths between vertices. Following the study of the graph geometry we proceed to its random perturbation via exponential weights on the edges (first-passage-percolation). We then show how this allows the derivation of various key features of the classical Erd\H{o}s-R\'enyi random graph near criticality, such as the asymptotics of the diameter of the largest component and the mixing time of the random walk on it. Based on joint works with Jian Ding, Jeong Han Kim, Yuval Peres and Allan Sly.

Host: Jacques Verstraete

February 18, 2010

3:00 PM

AP&M 6402

****************************