14h00: Christina Goldschmidt, University of Warwick.

The scaling limit of critical random graphs.

Consider the Erdos-Renyi random graph G(n,p): we have n vertices, every pair of which is joined by an edge independently with probability p. As is well known, this model undergoes a phase transition as p passes through 1/n. Below 1/n, there are only "small" components; above, there is one so-called giant component, which contains a positive proportion of the vertices. We are interested in the "critical window", where p = n^{-1} + \lambda n^{-4/3} for some real \lambda. In this regime, the largest components are of size n^{2/3} and have finite surpluses (where the surplus of a component is the number of edges more than a tree that it has). Using a bijective correspondence between graphs and certain "marked random walks", we are able to give a (surprisingly simple) metric space description of the scaling limit of the ordered sequence of components, where edges in the original graph are re-scaled by n^{-1/3}. A limit component, given its size and surplus, is obtained by taking a continuum random tree (which is not a Brownian CRT, but one whose distribution has been exponentially tilted) and making certain natural vertex identifications, which correspond to the surplus edges. This gives a metric space in which distances are calculated using paths in the original tree and the "shortcuts" induced by the vertex identifications. The limit of the whole critical random graph is then a collection of such metric spaces. The convergence holds in a sufficiently strong sense (an appropriate version of the Gromov-Hausdorff distance) that we are able to deduce the convergence in distribution of the diameter of G(n,p), re-scaled by n^{-1/3}, to a non-degenerate random variable, for p in the critical window. This is joint work with Louigi Addario-Berry (McGill University) and Nicolas Broutin (INRIA Rocquencourt).