Airy Phenomena and Analytic Combinatorics of Connected Graphs

Philippe Flajolet 1 Bruno Salvy 1 Gilles Schaeffer
1 ALGO - Algorithms
Inria Paris-Rocquencourt
Abstract : Until now, the enumeration of connected graphs has been 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. In this perspective, the enumeration of connected graphs by excess (of number of edges over number of vertices) derives from a simple saddle-point analysis. Furthermore, a refined analysis based on coalescent saddle points yields complete asymptotic expansions for the number of graphs of fixed excess, through an explicit connection with Airy functions.
Document type :
Reports
Complete list of metadatas

https://hal.inria.fr/inria-00072004
Contributor : Rapport de Recherche Inria <>
Submitted on : Tuesday, May 23, 2006 - 7:31:14 PM
Last modification on : Friday, May 25, 2018 - 12:02:02 PM
Long-term archiving on : Sunday, April 4, 2010 - 10:48:30 PM

Identifiers

  • HAL Id : inria-00072004, version 1

Collections

Citation

Philippe Flajolet, Bruno Salvy, Gilles Schaeffer. Airy Phenomena and Analytic Combinatorics of Connected Graphs. [Research Report] RR-4581, INRIA. 2002. ⟨inria-00072004⟩

Share

Metrics

Record views

99

Files downloads

163