Martedi' 22 ottobre 2013, alle 14.30, nell'Aula B  del  Dip. di Matematica dell'Universita' La Sapienza,  si terra' si seguente seminario 

Speaker: Pietro Caputo (Universita' di Roma III)

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

approach

Abstract:

Consider the Erdos-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.

Prof. Alessandra Faggionato