Ravelomanana

Le Jeudi 23 Novembre 2000 à 14h30

Salle de Conférences du LIX, École Polytechnique

V. Ravelomanana

(LRI)

Aspects combinatoires des graphes sans isomorphisme

Résumé/Abstract : L'énumération de graphes étiquetés trouve ses origines quand, vers 1880, A. Cayley compta le nombre d'étiquetages d'arbres pouvant être construits sur n sommets. Depuis, les graphes multicycliques connexes (possédant n sommets et n+k arêtes) ont été énumérés par E. M. Wright de manière exacte et asymptotiquement par E. Bender et al. Toutefois, les problèmes combinatoires soulevés par les énumérations des graphes sans triangle (sans carré, ...) s'avèrent difficiles.

Étant donné un ensemble fini, , de motifs interdits, le but de cet exposé est d'introduire une équation fonctionnelle (type ``conduction de la chaleur'') satisfaite par les séries génératrices des graphes sans . Nous montrerons sur quelques exemples, comment résoudre une telle équation et obtenir les séries génératrices des premiers multicycles sans . Nous montrerons alors que ces séries génératrices se présentent toutes sous une forme particulière permettant de compter asymptotiquement les graphes sans avec n sommets et n+o(n1/3) arêtes. Nous verrons alors les conséquences de ces énumérations dans divers modèles de graphes aléatoires.