Airy phenomena and analytic combinatorics of connected graphs
type: Item
instance of: scholarly article
title: Airy phenomena and analytic combinatorics of connected graphs
zbMATH Open document ID: 1053.05064
author: Philippe Flajolet
author: Bruno Salvy
author: Gilles Schaeffer
published in: The Electronic Journal of Combinatorics
publication date: 2004-10-13T00:00:00Z
full work available at URL: https://eudml.org/doc/124015
full work available at URL: v11i1r34.html
review text: Summary: 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.
Mathematics Subject Classification ID: 05C30
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05A16
Mathematics Subject Classification ID: 05C40
Mathematics Subject Classification ID: 05C80
zbMATH DE Number: 2107476
zbMATH Keywords: enumeration
zbMATH Keywords: connected graphs
zbMATH Keywords: saddle-point method
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 2107476