Laboratoire d'informatique de l'École polytechnique

Exposé par Nathan Noiry: «L'algorithme de parcours en profondeur dans un modèle de configuration»

Speaker: Nathan Noiry
Location: Salle Philippe Flajolet, LIX
Date: Mer. 29 janv. 2020, 10h30-11h30

La prochaine séance du séminaire Combi du Plateau de Saclay aura lieu ce mercredi à 10h30 dans la salle Philippe Flajolet du LIX. Nathan Noiry (Modal’X, Université Paris Nanterre) nous parlera de «L’algorithme de parcours en profondeur dans un modèle de configuration».

Le programme du séminaire est disponible ici : https://galac.lri.fr/pages/combi-seminar.html

Résumé: 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 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.