Groupe de Travail de l'équipe “Probabilités & Statistiques de l'Institut Élie Cartan (Nancy)
7 novembre 2013 : Philippe Chassaing
ζ(3) & Processus de Poisson

Considérant un graphe dont les arêtes sont pondérées, un problème classique en informatique fondamentale (ou en optimisation combinatoire) est celui de la recherche de l'arbre couvrant de poids minimal de ce graphe — le poids d'un arbre couvrant étant la somme des poids de ses arêtes. Ici nous allons considérer un graphe à n sommets dont les arêtes sont pondérées aléatoirement : plus précisément, nous supposons que les poids des arêtes forment une famille i.i.d. de v.a. positives, dont la fonction de répartition est notée F. Alan Frieze a montré que, sous des hypothèses très contraignantes sur F, le poids de l'arbre couvrant minimal converge vers ζ(3) × limx→0{F(x)/x} quand n tend vers l'infini.

La méthode objective d'Aldous permet de généraliser ce résultat et de l'interpréter de manière frappante comme un calcul d'espérance de fonctionnelle de processus de Poisson, ce que j'essaierai d'expliquer de manière élémentaire. Ensuite, si le temps le permet, je parcourrai quelques résultats récents de mécanique statistique obtenus à l'aide de la susdite méthode objective.