Top-level heading

Large deviations in sparse random graphs: a local weak convergence approach

Data e ora inizio evento
Data e ora fine evento
Sede

Dipartimento di Matematica Guido Castelnuovo, Sapienza Università di Roma

Aula
Aula B
Speaker

PIETRO CAPUTO (Università Roma Tre)

Consider the Erdös-Renyi random graph on n vertices where each edge is present independently with probability p=c/n, with c>0 fixed. For large n, a typical realization locally behaves like the Galton-Watson tree with Poisson offspring distribution with mean c. We discuss large deviations from this typical behavior, within the framework of the local weak convergence introduced by Benjamini-Schramm and Aldous-Steele. The associated rate function is expressed in terms of an entropy functional on unimodular measures and takes finite values only at measures supported by trees. Along the way, we present a new configuration model which allows one to sample uniform random graphs with a given finite neighborhood distribution, provided the latter is supported by trees. We also present a new class of unimodular random trees, which generalizes the Galton-Watson tree with given degree distribution to the case of neighborhoods of arbitrary finite depth. This is joint work with Charles Bordenave.