L’algorithme de parcours en profondeur dans un modèle de configuration

Dans cet exposé, issu d’un travail en collaboration avec Nathanaël Enriquez, Gabriel Faraud et Laurent Ménard, nous nous intéresserons à des graphes aléatoires dont la suite des degrés est fixée. Nous verrons que ce modèle présente une transition de phase concernant l’existence d’une composante connexe de taille macroscopique. Dans le régime surcritique, nous nous intéresserons à l’algorithme de parcours en profondeur sur cette composante géante, qui en construit un arbre couvrant. Notre résultat principal établit la convergence du processus de contour renormalisé associé à cet arbre, vers un profil limite et explicite. Une conséquence de ce résultat est l’existence de chemins simples macroscopiques dans le graphe.

Nous aborderons ensuite quelques éléments de preuve et verrons qu’au cours de l’exploration, l’évolution de la mesure empirique des degrés au sein du graphe induit par les sommets non-explorés admet une limite fluide. Celle-ci est décrite par un système infini d’équations différentielles qui, de manière inattendue, admet une solution unique et explicite en fonction de la série génératrice de la loi initiale des degrés.