GdTProbaTESD20200127

Limiting spectrum of sparse graphs

Lundi 27 janvier 2020, 11:00 à 12:00

Salle de séminaire M.0.1.

Simon Coste

(INRIA, Paris)

In this introductory talk, I will present a general limiting
theory for the spectrum of large networks. The models I will consider
are quite general, but they share a common feature : all of them are
studied in their very sparse regime where the number of connections has
the same order as the number of nodes (Erdös-Rényi with fixed mean
degree, regular graphs, uniform trees, uniform triangulations,
preferential attachments). The spectrum of such networks is notoriously
different than in the more classical denser regime, in which it usually
belongs to the "Wigner universality class" and converges towards a
semi-circle. In our sparse regimes, things are really more complicated
and to a large extent, still very mysterious. Limiting spectra exhibit
strange shapes, with possibly unbounded support, sometimes with atoms. I
will show many pictures of such spectra, then give an overview of the
(beautiful) Benjamini-Schramm theory and spectral continuity theorem,
and finally survey the few known results on the limiting spectrum of
sparse graphs. This is based on joint work with Justin Salez.