GRaphes et Arbres ALéatoires – GRAAL

Ces dix dernières années ont vu se développer une intense activité de recherche sur les limites d'échelle
de graphes aléatoires et de cartes aléatoires. Ces questions probabilistes sont motivées par des modèles de
physique et les résultats obtenus reposent souvent sur des constructions combinatoires sophistiquées.
Deux des principaux outils utilisés pour ces résultats sont d'une part des bijections entre cartes et arbres, et
d'autre part un ensemble de résultats sur les limites d'échelle d'arbres, développés dans les années 90.
L'un des résultats phare est l'unicité de la carte Brownienne, obtenue récemment. Le projet GRAAL
rassemblera la plupart des meilleurs spécialistes français sur les graphes, arbres et cartes aléatoires, dans le
domaine discret aussi bien que dans le domaine continu. Ce projet a pour but d'approfondir
la compréhension des liens existant entre graphes, arbres et cartes dans trois directions interdépendantes.

1. Cartes planaires.

Un de nos premiers buts est d'obtenir une description précise des propriétés géométriques et
probabilistes de la carte Brownienne. L'étape suivante, particulièrement importante du point de vue physique est
de considérer les cas de cartes planaires munies d'un modèle de mécanique statistique (percolation, marche aléatoire,
modèle de Potts, modèle O(N) ...). Pour certains de ces modèles, il reste à développer des outils
combinatoires avant de pouvoir envisager des questions sur leurs propriétés probabilistes et asymptotiques.
Un point clef de cette approche serait une unification des bijections pour les cartes planaires,
avant de considérer des généralisations non-planaires. Cela devrait également ouvrir la voie à l'étude métrique
des cartes non-planaires. Nos intérêts se tournent également vers des généralisations de la carte Brownienne, telles
que les cartes stables qui sont récemment apparues comme des limites d'échelle de cartes planaires décorées.
Un but important, à long terme, est d'établir une relation de ces limites d'échelle avec la gravité quantique de Liouville,
théorie des surfaces aléatoires basée sur le champ libre Gaussien bi-dimensionnel.

2. Arbres continus.

Nous envisageons d'explorer plus avant la convergence de grands arbres conditionnés, qui apparaissent naturellement
dans plusieurs applications (typiquement dans l'étude des cartes aléatoires ou dans l'analyse d'algorithmes).
Nous analyserons également les propriétés fines (propriétés géométriques, records ...) des arbres continus généraux
et nous nous intéressons à la construction de dynamiques à valeurs dans les arbres. Enfin, des classes d'arbres continus
non-classiques apparaissent comme limites de modèles de mécanique statistique qui sont jusqu'à présent difficiles à
appréhender: nous voulons développer quelques outils nouveaux facilitant leur étude.

3. Graphes aléatoires.

Nous nous intéressons à la limite d'échelle des graphes d'Erdös-Rényi lorsque le paramètre se situe dans la
fenêtre critique. A la limite, la taille des composantes connexes évolue comme un coalescent multiplicatif mais
la dynamique de tout l'espace est encore difficile à cerner. Nous nous intéressons également à la convergence
de l'arbre couvrant minimal associé vers une limite que nous pensons être universelle. Dans le domaine des graphes, d'autre
questions constituent des axes de recherche du projet: l'étude combinatoire des graphes à mineurs exclus, dans les cas où les
mineurs ne sont pas 2-connexes; dans une autre perspective, nous voulons également étudier
plusieurs modèles de graphes hiérarchiques qui semblent avoir des propriétés métriques intéressantes et qui sont liées à des
processus de branchement.