Phénomène d'Airy et Combinatoire Analytique des Graphes Connexes

Jusqu'à présent, le dénombrement des graphes connexes a été traité par des méthodes probabilistes, par des décompositions combinatoires particulières ou par des manipulations de séries assez indirectes. Nous montrons qu'il est possible de donner un sens analytique à la série divergente qui exprime la fonction génératrice des graphes connexes. En conséquence, il devient possible d'obtenir analytiquement des résultats de dénombrement connus en utilisant uniquement des principes élémentaires d'analyse combinatoire et de l'analyse asymptotique classique (la méthode du col). Dans cette perspective, le dénombrement des graphes connexes par excès (du nombre d'arêtes sur le nombre de sommets) se déduit d'une analyse de col simple. De plus, un raffinement de l'analyse fondée sur des points cols coalescents donne un développement asymptotique complet pour le nombre de graphes d'excès fixé, via une connection explicite avec les fonctions d'Airy.

Ce travail a été effectué en commun avec Philippe Flajolet et Gilles Schaeffer.