Retour à l'index du GREYC

Séminaire Algorithmique

Site du CNRS

Séminaire Algorithmique

Le séminaire a lieu le mardi à 11 h 45 (sauf modification exceptionnelle), au campus Côte de Nacre, bâtiment Sciences 3, salle S3 351, 3ème étage.

Résumé du séminaire du Mardi 18 Février 2020

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

par Nathan Noiry (Paris Ouest, Nanterre)

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.

GREYC
Campus Côte de Nacre, boulevard du Maréchal Juin
BP 5186
14032 Caen Cedex
FAX : +33 (0)2 31 56 73 30
http://www.greyc.fr