Résumé : Un arbre couvrant d'un graphe connexe fini G est un sous-graphe connexe de G qui contient chaque sommet et ne contient aucun cycle. Un résultat bien connu d'Aldous énonce que la limite d'échelle de l'arbre couvrant uniforme du graphe complet est l'arbre brownien. En fait cet énoncé est plus général : l'arbre brownien est la limite d'échelle des arbres couvrants uniformes pour un grand ensemble de graphes en grande dimension. Dans cet exposé, nous allons essayer d'expliquer ce phénomène universel, à l'aide des algorithmes d'échantillonnage. Si le temps nous permet, nous allons également discuter des limites d’échelle des arbres couvrants aléatoires non-uniformes. Travaux en collaboration avec Asaf Nachmias et Matan Shalev.

 [arXiv] [vidéo]

Dernière modification : Monday 27 May 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr