Grégory Miermont (ENS de Lyon)

"La limite d'échelle de l'arbre couvrant minimal du graphe complet "

Supposons que chaque arête d'un graphe soit munie d'un nombre réel (son poids). On cherche alors l'arbre couvrant du graphe pour lequel la somme des poids des arêtes est la plus petite possible. Trouver cet arbre couvrant minimal est un des problèmes d'optimisation combinatoire les plus simples, que l'on résout par un algorithme glouton élémentaire. Dans cet exposé, on s'intéressera au cas où le graphe est le graphe complet à n sommets, et où les poids sont des variables aléatoires indépendantes de même loi diffuse. L'arbre couvrant minimal associé est un arbre aléatoire à n sommets, et on étudiera sa géométrie lorsque n tend vers l'infini. Plus précisément, on montrera que les distances typiques dans cet arbre sont de l'ordre de n^{1/3}, et qu'après renormalisation par cette quantité, l'arbre approche un R-arbre aléatoire limite pour la distance de Gromov-Hausdorff, dont la dimension de Minkowski est égale à 3 presque-sûrement.

D'après un travail en collaboration avec Louigi Addario-Berry, Nicolas Broutin et Christina Goldschmidt.