### Random regular graphs: from spectrum to geometry and back

- Series
- ACO Seminar
- Time
- Friday, October 23, 2009 - 15:05 for 1 hour (actually 50 minutes)
- Location
- Skiles 255
- Speaker
- Eyal Lubetzky – Microsoft Research, Redmond, WA

The class of random regular graphs has been the focus of extensive study highlighting
the excellent expansion properties of its typical instance. 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 their spectrum and geometry.
We will first discuss the relation between spectral properties and the abrupt
convergence of the simple 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
properties of the classical Erd\H{o}s-R\'enyi random graph near criticality. Finally,
returning to the spectrum of random regular graph, we discuss the question of how
close they really are to being Ramanujan and conclude with related problems involving
random matrices.
Based on joint works with Jian Ding, Jeong Han Kim and Yuval Peres, with Allan Sly
and with Benny Sudakov and Van Vu.