Séminaire Philippe Flajolet

Processus d’épluchage pour les DAGs par les séries graphiques et génération aléatoire

par Martin Pépin (GREYC, Université Caen Normandie)

→ Europe/Paris
Amphithéâtre Choquet Bruhat (IHP Bâtiment Perrin)

Amphithéâtre Choquet Bruhat

IHP Bâtiment Perrin

Description

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.