×

zbMATH — the first resource for mathematics

Random maps, coalescing saddles, singularity analysis, and Airy phenomena. (English) Zbl 1016.68179
Summary: 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 \({3\over 2}\)) 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.

MSC:
68W20 Randomized algorithms
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] and Handbook of mathematical functions, Dover, New York 1973. [A reprint of the tenth National Bureau of Standards edition, 1964].
[2] and Planar maps and Airy phenomena, Automata, languages, and programming (2000), (Editors), Lecture Notes in Computer Science 1853, pp. 388-402 Proceedings of the 27th ICALP Conference, Geneva, July 2000.
[3] and Advanced mathematical methods for scientists and engineers. I. Springer-Verlag, New York, 1999. [Asymptotic methods and perturbation theory, Reprint of the 1978 original]. · doi:10.1007/978-1-4757-3069-2
[4] Bender, J Combin Theory 15 pp 91– (1973) · Zbl 0242.05006 · doi:10.1016/0097-3165(73)90038-1
[5] Bender, SIAM Review 16 pp 485– (1974) · Zbl 0294.05002 · doi:10.1137/1016082
[6] Bender, Bull Inst Combin Appl 3 pp 51– (1991)
[7] Bender, Rand Struct Alg 7 pp 273– (1995) · Zbl 0839.05090 · doi:10.1002/rsa.3240070402
[8] and Asymptotic Expansions of Integrals. Dover, New York, 1986. [A reprint of the second Holt, Rinehart and Winston edition, 1975].
[9] Bo, Meth Appl Anal 1 pp 294– (1994)
[10] Bollob?s, Rand Struct Alg 18 pp 201– (2001) · Zbl 0979.68053 · doi:10.1002/rsa.1006
[11] Bousquet-M?lou, Adv Appl Math 24 pp 337– (2000) · Zbl 0955.05004 · doi:10.1006/aama.1999.0673
[12] Probability, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1992. [Corrected reprint of the 1968 original]. · doi:10.1137/1.9781611971286
[13] Asymptotic methods in analysis, Dover, New York 1981. [A reprint of the third North Holland edition, 1970 (first edition, 1958)].
[14] Drmota, SIAM J Discrete Math 10 pp 246– (1997) · Zbl 0867.05001 · doi:10.1137/S0895480194268421
[15] Duchon, Ann Combin 3 pp 311– (1999) · Zbl 0939.05025 · doi:10.1007/BF01608790
[16] Probability: Theory and examples, 2nd ed. Duxbury Press, Belmont, CA, 1996.
[17] Higher transcendental functions, 2nd ed., vols. 1-3, Krieger, Malabar, FL, 1981.
[18] An introduction to probability theory and its applications, 2nd ed. vol. II, Wiley, New York, 1971.
[19] Flajolet, Theor Comput Sci 215 pp 371– (1999) · Zbl 0913.68098 · doi:10.1016/S0304-3975(98)00220-5
[20] Flajolet, Discrete Math 75 pp 167– (1989) · Zbl 0696.05045 · doi:10.1016/0012-365X(89)90087-3
[21] and Analytic variations on the Airy distribution, Technical Report TR-01-15, Alcom-FT Project, 2001. [To appear in Algorithmica, Special Issue on Analysis of Algorithms 2002; 16p]. · Zbl 1064.68065
[22] Flajolet, SIAM J Applied Math 3 pp 216– (1990)
[23] Flajolet, Algorithmica 22 pp 490– (1998) · Zbl 0914.68105 · doi:10.1007/PL00009236
[24] and Airy phenomena and analytic combinatorics of connected graphs, Research report, Institut National de Recherche en Informatique et en Automatique, 2001, in preparation.
[25] Flajolet, Discrete Math 114 pp 159– (1993) · Zbl 0776.60013 · doi:10.1016/0012-365X(93)90364-Y
[26] Frenzen, SIAM J Math Anal 19 pp 1232– (1988) · Zbl 0654.33004 · doi:10.1137/0519087
[27] Gao, SIAM J Discrete Math 12 pp 217– (1999) · Zbl 0923.05030 · doi:10.1137/S0895480195292053
[28] Gardy, Discrete Math 139 pp 189– (1995) · Zbl 0827.41023 · doi:10.1016/0012-365X(94)00133-4
[29] and Combinatorial enumeration, Wiley, New York, 1983.
[30] Ramanujan: Twelve lectures on subjects suggested by his life and work, 3rd ed. Chelsea, New York, 1978. [Reprinted and Corrected from the 1st ed., Cambridge, 1940].
[31] Th?or?mes limites pour les structures combinatoires et les fonctions arithmetiques, Ph.D. thesis, ?cole Polytechnique, 1994.
[32] Janson, Rand Struc Alg 4 pp 233– (1993) · Zbl 0795.05127 · doi:10.1002/rsa.3240040303
[33] Knuth, Algorithmica 22 pp 561– (1998) · Zbl 0918.68079 · doi:10.1007/PL00009240
[34] Random graphs, Encyclopedia of Mathematics and its Applications, vol. 53, Cambridge University Press, Cambridge, 1999.
[35] Liskovets, J Combin Theory Ser B 75 pp 116– (1999) · Zbl 0930.05050 · doi:10.1006/jctb.1998.1870
[36] Louchard, Comput Math Appl 10 pp 413– (1984) · Zbl 0569.65097 · doi:10.1016/0898-1221(84)90071-3
[37] Meir, Can J Math 30 pp 997– (1978) · Zbl 0394.05015 · doi:10.4153/CJM-1978-085-0
[38] Asymptotic enumeration methods, Handbook of combinatorics, vol. II, and (Editors), Elsevier, Amsterdam, 1995, pp. 1063-1229.
[39] Asymptotics and special functions, Academic Press, New York, 1974. · Zbl 0303.41035
[40] Generating functions with high-order poles are nearly polynomial, Mathematics and computer science (Versailles, 2000). Birkh?user, Basel, 2000, pp. 305-321. · Zbl 0984.05007 · doi:10.1007/978-3-0348-8405-1_26
[41] Prellberg, J Phys A: Math Gen 28 pp 1289– (1995) · Zbl 0852.33011 · doi:10.1088/0305-4470/28/5/016
[42] Richmond, J Combin Theory Ser B 63 pp 1– (1995) · Zbl 0820.05017 · doi:10.1006/jctb.1995.1001
[43] Conjugaison d’arbres et cartes combinatoires al?atoires, Ph.D. thesis, Universit? Bordeaux I, 1998.
[44] Random sampling of large planar maps and convex polyhedra, Proc of the 31st Annual ACM Symposium on Theory of Computing (STOC’99), Atlanta, Georgia, 1999, ACM, New York, pp. 760-769. · Zbl 1345.05105
[45] M?thodes d’analyse pour les constructions combinatoires et les algorithmes, Doctorate in sciences, Universit? de Paris-Sud, Orsay, 1990.
[46] Spencer, Commun Pure Appl Math 50 pp 293– (1997) · Zbl 0871.05032 · doi:10.1002/(SICI)1097-0312(199703)50:3<291::AID-CPA4>3.0.CO;2-6
[47] Takacs, Adv Appl Probab 23 pp 557– (1991) · doi:10.1017/S0001867800023739
[48] Tutte, Can J Math 15 pp 249– (1963) · Zbl 0115.17305 · doi:10.4153/CJM-1963-029-x
[49] Planar enumeration, Graph theory and combinatorics (Cambridge, 1983), Academic Press, London, 1984, pp. 315-319.
[50] A treatise on the theory of Bessel functions, Cambridge University Press, Cambridge, 1980.
[51] and A course of modern analysis, 4th ed. Cambridge University Press, Cambridge, 1927. [Reprinted 1973].
[52] Asymptotic approximations of integrals, Academic Press, New York, 1989. · Zbl 0679.41001
[53] One-dimensional stable distributions, American Mathematical Society, Providence, RI, 1986. [Translated from the Russian by H.H. McFaden, Translation edited by Ben Silver.]
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.