Vlady Ravelomanana (Universite d'Amiens)

L’enumeration de graphes etiquetes trouve ses origines quand, vers 1880, A. Cayley compta le nombre d’‘etiquetages d’arbres pouvant etre construits sur $n$ sommets. Depuis, les graphes multicycliques connexes (possedant $n$ sommets et $n+k$ ar\^etes) ont ete enumeres par E.~M. Wright de maniere exacte et asymptotiquement par E. Bender et al.. Toutefois, les problemes combinatoires souleves par les enumerations des graphes sans triangle (sans carres) s’averent difficiles.

Etant donne un ensemble fini, $\xi$, de motifs interdits, le but de cet expose est d’introduire une equation fonctionnelle (type ``conduction de la chaleur’’) satisfaite par les series generatrices des graphes sans $\xi$. Nous montrerons sur quelques exemples, comment resoudre une telle equation et obtenir les series generatrices des premiers multicycles sans $\xi$. Nous montrerons alors que ces series generatrices se presentent toutes sous une forme particuliere permettant de compter asymptotiquement les graphes sans $\xi$ avec $n$ sommets et $n+o(n^{1/3}) aretes. Nous verrons alors les consequences de ces enumerations dans divers modeles de graphes aleatoires (et ce par l’approche enumerative).