Random Graphs and Trees – GRAAL

The past ten years have witnessed an intense research activity
on the scaling limits of random graphs and random maps.
These probabilistic questions are motivated by physics models,
and the results that have been obtained often rely on sophisticated
combinatorial constructions. Two of the main tools involved in those
results are bijections between maps and trees, and a collection of
known results dealing with the scaling limits of trees, both developed
in the 90's. One of the major recent achievements is the uniqueness
of the so-called Brownian map. The GRAAL project will gather most
of the French specialists of random graphs, trees and maps, both in
the discrete and continuous settings. It aims at deepening our
understanding of the links that tie graphs, trees and maps, in three
interdependent directions.

1. Planar maps

We first aim at a precise description of the geometric and probabilistic
properties of the Brownian map. The next step, which is highly relevant
from a physics point of view, is to consider planar maps endowed with
a statistical mechanics model (percolation, random walks, Potts model,
O(N) model ...). For some of those models, we still need to develop
combinatorial tools before one can address probabilistic and asymptotic
questions. A key tool relies in the unification of bijections for planar maps,
before their extension to non-planar maps. This should open the way to
the study of metric properties of non-planar maps. We are also interested
in generalizations of the Brownian map, such as the so-called stable maps
which appeared recently as the scaling limit of decorated planar maps.
One major long term goal is to establish the relation of those scaling limits
to the so-called Liouville Quantum Gravity, the theory of random surfaces
based on the two-dimensional Gaussian Free Field.

2. Continuum trees

We plan to investigate further the convergence of large conditioned random
trees that appear naturally in various applications (typically in the study of
random maps or in the analysis of algorithms). We will also analyze fine
properties (for instance geometric properties and the record process) of
general continuum trees, and design and study tree-valued dynamics.
Finally, non-classical continuum random trees appear as limits of others
statistical mechanics models but are so far difficult to handle: we plan to
develop new tools for their study.


3. Random graphs

We want to further investigate the scaling limit of Erdös-Rényi graphs
when the parameter ranges in the critical window. At the limit, the
sizes of the connected components evolve as a multiplicative coalescent
but the dynamic of the whole limiting metric spaces remains elusive.
We shall also consider the convergence of the associated minimum
spanning trees and prove that the limiting tree is an universal object.
We also want to study graphs with excluded minors, in the cases where
the minors are not 2-connected. We also want to investigate several
hierarchical graphs with nice metric structures and with which branching
processes are involved.