La limite continue de l'arbre couvrant minimal d'un graphe complet

par Jean-François Marckert (LaBRI)

mardi 16 déc. 2025, 09:50 → 10:50 Europe/Paris

On considère le graphe complet à n sommets K_n, dont les arêtes sont munies de poids aléatoires indépendants, mettons, uniformes sur [0,1]. On définit alors le poids d'un arbre (inclu dans K_n) comme étant la somme des poids des arêtes qu'il contient; l'arbre couvrant minimal T_n est l'arbre couvrant de K_n de poids minimal. Il est presque sûrement bien défini, et aléatoire, ça va sans dire; et ajoutons qu'une fois qu'on a trouvé T_n, on le regarde comme un arbre combinatoire, sans poids, et on se demande à quoi il ressemble... sa loi, son échelle, sa forme, et les limites de celles-ci, lorsque n tend vers l'infini.

Addario-Berry, Broutin, Goldschmidt et Miermont, en 2017, on démontré que si on normalise les distances d_{T_n}(.,.) dans T_n par n^{1/3} , alors, (T_n,d{T_n}(.,.)/n^{1/3}) , vu comme espace métrique aléatoire, possède une limite en loi: un arbre continu aléatoire. L'argument de AB-B-G-M est un argument de compacité, et seule l'existence de la limite, et certaines de ses propriétés sont obtenues (c'est un arbre binaire de dimension de Minkowski 3), par contre, la limite n'est pas identifiée.

Dans ce travail, nous identifions la limite, et nous l'appelons "l'arbre parabolique brownien". Il s'agit d'un nouvel objet, construit à l'aide des minorants convexes d'un mouvement brownien avec drift parabolique (l'ensemble des minorants convexes de la courbe sur [0,x], pour tout x).

Le but de l'exposé est de présenter cet objet, et d'expliquer, à l'aide principalement d'argument probabilisto-combinatoire, pourquoi il apparaît comme limite de l'arbre couvrant minimal. 

Travail commun Nicolas Broutin (Université Sorbonne, Paris)