Random Maps, Coalescing Saddles, Singularity Analysis, and Airy Phenomena

Cyril Banderier 1 Philippe Flajolet 1 Gilles Schaeffer 2 Michele Soria 3
2 ADAGE - Applying discrete algorithms to genomics
INRIA Lorraine, LORIA - Laboratoire Lorrain de Recherche en Informatique et ses Applications
3 CALFOR - Calcul formel
LIP6 - Laboratoire d'Informatique de Paris 6
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 random 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. Based on an extension of the singularity analysis framework suggested by the Airy case, the paper also presents a general classification of compositional schemas in analytic combinatorics.
Type de document :
Article dans une revue
Random Structures and Algorithms, Wiley, 2001, 19 (3-4), pp.194-246
Liste complète des métadonnées

Contributeur : Publications Loria <>
Soumis le : jeudi 19 octobre 2006 - 15:13:01
Dernière modification le : dimanche 9 décembre 2018 - 01:24:47


  • HAL Id : inria-00108014, version 1


Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michele Soria. Random Maps, Coalescing Saddles, Singularity Analysis, and Airy Phenomena. Random Structures and Algorithms, Wiley, 2001, 19 (3-4), pp.194-246. 〈inria-00108014〉



Consultations de la notice