Evènement pour le groupe Combinatoire Énumérative et Algébrique


Date 2013-01-25  10:45-11:45
TitrePropriétés asymptotiques de quelques classes de graphes à mineurs exclus 
RésuméSoit A une classe de graphes étiquetés, fermée pour l'extraction de mineurs. Soit G_n un graphe aléatoire de taille n pris uniformément dans A. Quand n est grand, quelle est la probabilité que G_n soit connexe ? Plus généralement, combien de composantes connexes a-t-il ? Grâce aux travaux de McDiarmid et de ses collaborateurs, ces questions sont désormais résolues lorsque tous les mineurs interdits sont connexes. C'est par exemple le cas des graphes planaires. Nous étudions, via une énumération exacte, une collection de classes A définies par l'interdiction de mineurs dont certains ne sont pas 2-connexes, et montrons que leur propriétés asymptotiques peuvent être très différentes de celles obtenues dans le cas de mineurs 2-connexes. Ces propriétés dépendent de la nature des singularités dominantes de la série génératrice C(z) qui compte les graphes connexes de A. Nous classons nos exemples selon cette nature, ce qui constitue un premier pas (modeste) vers une classification complète des classes de graphes closes par extraction de mineurs. (travail en commun avec Kerstin Weller, Oxford) 
Lieu076 
OrateurMireille Bousquet-Mélou 



Aucun document lié à cet événement.

Retour
Retour à l'index