Planar maps and Airy phenomena

Cyril Banderier 1 Philippe Flajolet 1 Gilles Schaeffer 2 Michele Soria 3
2 POLKA - Polynomials, Combinatorics, Arithmetic
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 $(e^{-x^2})$, that is, Gaussian. We exhibit here a new class of ``universal'' phenomena that are of the exponential-cubic type ($e^{ix^3}$), corresponding to nonstandard distributions that involve the Airy function. Such Airy phenomena are expected to be found in a number of applications, when confluences of critical points and singularities occur. About a dozen classes of planar maps are treated in this way, leading to the occurrence of a common Airy distribution that 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.
Type de document :
Communication dans un congrès
U. Montanari, J. Rolim, E. Welzl. International Colloquium on Automata, Languages, & Programming - ICALP'2000, Jul 2000, Genève, Switzerland. Springer, 1853, pp.388-402, 2000, Lecture Notes in Computer Science. 〈10.1007/3-540-45022-X_33〉
Liste complète des métadonnées

https://hal.inria.fr/inria-00099359
Contributeur : Publications Loria <>
Soumis le : mardi 26 septembre 2006 - 08:53:17
Dernière modification le : jeudi 22 novembre 2018 - 14:45:33

Lien texte intégral

Identifiants

Citation

Cyril Banderier, Philippe Flajolet, Gilles Schaeffer, Michele Soria. Planar maps and Airy phenomena. U. Montanari, J. Rolim, E. Welzl. International Colloquium on Automata, Languages, & Programming - ICALP'2000, Jul 2000, Genève, Switzerland. Springer, 1853, pp.388-402, 2000, Lecture Notes in Computer Science. 〈10.1007/3-540-45022-X_33〉. 〈inria-00099359〉

Partager

Métriques

Consultations de la notice

118