Expander graphs and the spectral gap of random regular graphs (Antti Knowles, Université de Genève)

16.09.2019 15:15

Expander graphs are sparse graphs with good connectivity properties. I review some basics of expander graphs, and in particular explain a spectral characterization of the expansion properties of regular graphs in terms of the spectral gap. I then explain how fluctuations of the spectral gap can be analysed for random regular graphs whose degree grows with the number of vertices. This shows that approximately 27% of all regular graphs are optimal expanders.

Lieu

Room 17, Séminaire "Mathématique Physique"

entrée libre