Projet ANR-14-CE25-0014 – GRAAL : GRaphes et Arbres ALéatoires
Programme : Défi de tous les savoirs (DS10) 2014
Année de financement : 2014
Coordinateur du projet : Monsieur Thomas Duquesne (Laboratoire de Probabilités et Modèles Aléatoires, UMR7599, Université P. et M. Curie)
Partenaires : Institut Élie Cartan de Lorraine; Laboratoire Bordelais de Recherche en Informatique; Laboratoire public
Montant : 441603.0 euros
Date de début : 2014
Durée : 60 mois
Résumé : 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.