Airy Phenomena and Analytic Combinatorics of Connected Graphs

Philippe Flajolet 1 Bruno Salvy 1 Gilles Schaeffer 2
1 ALGO - Algorithms
Inria Paris-Rocquencourt
2 ADAGE - Applying discrete algorithms to genomics
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
Abstract : The enumeration of connected graphs has been so far dealt with by probabilistic methods, by special combinatorial decompositions or by somewhat indirect formal series manipulations. We show here that it is possible to make analytic sense of the divergent series that expresses the generating function of connected graphs. As a consequence, it becomes possible to derive analytically known enumeration results using only first principles of combinatorial analysis and straight asymptotic analysis---specifically, the saddle-point method. The enumeration of connected graphs by excess derives from a simple saddle-point analysis; furthermore, a refined analysis based on coalescent saddle points yields an explicit connection with Airy functions.
Type de document :
Rapport
[Intern report] A02-R-216 || flajolet02a, 2002, 25 p
Liste complète des métadonnées

https://hal.inria.fr/inria-00101063
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 14:55:10
Dernière modification le : vendredi 25 mai 2018 - 12:02:02

Identifiants

  • HAL Id : inria-00101063, version 1

Citation

Philippe Flajolet, Bruno Salvy, Gilles Schaeffer. Airy Phenomena and Analytic Combinatorics of Connected Graphs. [Intern report] A02-R-216 || flajolet02a, 2002, 25 p. 〈inria-00101063〉

Partager

Métriques

Consultations de la notice

111