Processus d’épluchage pour les DAGs par les séries graphiques et génération aléatoire
par
Amphithéâtre Choquet Bruhat
IHP Bâtiment Perrin
L'étude des graphes dirigés sans cycles (DAG) par le biais des séries génératrices remonte au moins aux travaux de Robinson dans les année 1970. En introduisant un type de séries spécifique à l'étude des DAGs, il y établit des récurrences, ainsi que des résultats asymptotiques. Avec le recul apporté par la combinatoire analytique, ces travaux ont été remis au goût du jours ces dernières années, notamment afin étudier les DAGs d'un point de vue structurel.
Dans cet exposé, je présenterai une approche nouvelle sur l'énumération des DAGs via un processus d'épluchage et comment ce processus se traduit en terme de séries dites "graphiques". Nous verrons que cette approche offre un point de vue probabiliste nouveau sur les DAGs et donne accès à un algorithme de génération aléatoire efficace.