Premium
Random maps, coalescing saddles, singularity analysis, and Airy phenomena
Author(s) -
Banderier Cyril,
Flajolet Philippe,
Schaeffer Gilles,
Soria Michèle
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.10021
Subject(s) - airy function , exponent , mathematics , gravitational singularity , exponential function , planar , singularity , combinatorics , quadratic equation , gaussian , generating function , mathematical analysis , geometry , physics , quantum mechanics , computer science , philosophy , linguistics , computer graphics (images)
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 article, 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 random planar maps, a common Airy distribution (equivalently, a stable law of exponent \documentclass{article}\pagestyle{empty}\begin{document}$\frac{3}{2}$\end{document} ) describes the sizes of cores and of largest (multi)connected components. Consequences include the analysis and fine optimization of random generation algorithms for a multiple connected planar graphs. Based on an extension of the singularity analysis framework suggested by the Airy case, the article also presents a general classification of compositional schemas in analytic combinatorics. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19: 194–246, 2001