ALCOMFT-TR-01-20

Cyril Banderier, Philippe Flajolet, Gilles Schaeffer and Michele Soria
Random Maps, Coalescing Saddles, Singularity Analysis, and Airy Phenomena
INRIA. Work packages 4 and 5. March 2001.

Abstract: A considerable number of asymptotic distributions arising in random combinatorics and analysis of algorithms are of the exponential-quadratic type, that is, Gaussian. We exhibit a class of ``universal'' phenomena that are of the exponential-cubic type, corresponding to distributions that involve the Airy function. In this paper, such Airy phenomena are related to the coalescence of saddle points and the confluence of singularities of generating functions. For about a dozen types of planar maps, a common Airy distribution (equivalently, a stable law of exponent 3/2) describes the sizes of cores and of largest (multi)connected components. Consequences include the analysis and fine optimization of random generation algorithms for multiply connected planar graphs, as well as the general classification of compositional schemas in analytic combinatorics.

Postscript file: ALCOMFT-TR-01-20.ps.gz (780 kb).