skip to content

On the graph limit approach to random regular graphs

Presented by: 
Balazs Szegedy University of Toronto
Wednesday 13th July 2016 - 09:00 to 09:45
INI Seminar Room 1
Let G=G(n,d) denote the random d-regular graph on n vertices. A celebrated result by J. Friedman solves Alon's second eigenvalue conjecture saying that if d is fixed and n is large then G is close to be Ramanujan. Despite of significant effort, much less was known about the structure of the eigenvectors of G. We use a combination of graph limit theory and information theory to prove that every eigenvector of G (when normalized to have length equal to square root of n) has an entry distribution that is close to some Gaussian distribution in the weak topology. Our results also work in the more general setting of almost-eigenvectors. We hope our methods will lead to a general graph limit approach to a large class of problems on random regular graphs. Joint work with A. Backhausz.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons