Description

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.

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 that 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, a theory of random surfaces
based on the two-dimensional Gaussian Free Field.

map

Continuum trees

We plan to investigate further the convergence of large conditioned random trees that appear naturally in various applications (typically in Biology, 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 (such as non-crossing configuration, loop-trees) but are so far difficult to handle: we plan to develop new tools for their study.

CRT

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 minimum spanning trees of the complete graphs (strongly connected to E-R graphs) and prove that the limiting tree is an universal object. In two distinct directions, we plan to study graphs with excluded minors, in the cases where the minors are not 2-connected, and we also want to investigate several hierarchical graphs (close to toy models in quantum gravity) with nice metric structures and with which branching processes are involved.