×

The distribution of height and diameter in random non-plane binary trees. (English) Zbl 1250.05095

Summary: This study is dedicated to precise distributional analyses of the height of non-plane unlabelled binary trees (“Otter trees”), when trees of a given size are taken with equal likelihood. The height of a rooted tree of size \(n\) is proved to admit a limiting theta distribution, both in a central and local sense, and obey moderate as well as large deviations estimates. The approximations obtained for height also yield the limiting distribution of the diameter of unrooted trees. The proofs rely on a precise analysis, in the complex plane and near singularities, of generating functions associated with trees of bounded height.

MSC:

05C80 Random graphs (graph-theoretic aspects)
05C05 Trees

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aldous, The random walk construction of uniform spanning trees and uniform labelled trees, SIAM J Discr Math 3 pp 450– (1990) · Zbl 0717.05028
[2] Aldous, The continuum random tree I, Ann Probab 19 pp 1– (1991) · Zbl 0722.60013
[3] D. J. Aldous The continuum random tree II: An overview 1991 23 70
[4] Aldous, The continuum random tree III, Ann Probab 21 pp 248– (1993) · Zbl 0791.60009
[5] Bergeron, Combinatorial species and tree-like structures (1998) · Zbl 0888.05001
[6] Bóna, Isomorphism and symmetries in random phylogenetic trees, J Appl Probab 46 pp 1005– (2009) · Zbl 1231.60009
[7] N. Broutin P. Flajolet The height of random binary unlabelled trees 2008 121 134 · Zbl 1355.68061
[8] Chassaing, Parking functions, empirical processes, and the width of rooted labeled trees, Electron J Combin 8 pp 19– (2001) · Zbl 0974.05025
[9] Chassaing, In Mathematics and computer science (Versailles, 2000), Trends IN Mathematics pp 17– (2000)
[10] Chauvin, And/or trees revisited, Combin Probab Comput 13 pp 501– (2004) · Zbl 1077.94526
[11] de Bruijn, Asymptotic methods in analysis (1981) · Zbl 0556.41021
[12] de Bruijn, Graph theory and computing pp 15– (1972)
[13] Dembo, Large deviations techniques and applications (1993)
[14] Drmota, Random trees (2009) · Zbl 1170.05022
[15] M. Drmota B. Gittenberger The shape of unlabeled rooted random trees 2008
[16] Durrett, Functionals of Brownian meander and Brownian excursion, Ann Probab 5 pp 130– (1977) · Zbl 0356.60035
[17] Finch, Mathematical constants (2003)
[18] Flajolet, The average height of binary trees and other simple trees, J Comput Syst Sci 25 pp 171– (1982) · Zbl 0499.68027
[19] Flajolet, Analytic combinatorics (2009)
[20] Flajolet, The distribution of heights of binary trees and other simple trees, Combin Probab Comput 2 pp 145– (1993) · Zbl 0795.05042
[21] Flajolet, Mellin transforms and asymptotics: harmonic sums, Theor Comput Sci 144 pp 3– (1995) · Zbl 0869.68057
[22] Flajolet, On Ramanujan’s Q -function, J Comput Appl Math 58 pp 103– (1995) · Zbl 0826.33001
[23] D. Gardy Random Boolean expressions 2005 1 36
[24] Haas, Scaling limits of Markov branching trees, with applications to Galton-Watson and random unordered trees (2010) · Zbl 1259.60033
[25] Harary, Graphical enumeration (1973)
[26] Kennedy, The Galton-Watson process conditioned on the total progeny, J Appl Probab 12 pp 800– (1975) · Zbl 0322.60072
[27] Kennedy, The distribution of the maximum Brownian excursion, J Appl Probab 13 pp 371– (1976) · Zbl 0338.60048
[28] V. F. Kolchin Random Mappings, Optimization Software 1986 Slučajnye Otobraženija
[29] Kostrzycka, Asymptotic densities in logic and type theory, Stud Logic 88 pp 385– (2008) · Zbl 1142.03008
[30] Le Gall, Random trees and applications, Probab Surv 2 pp 245– (2005) · Zbl 1189.60161
[31] Lefmann, Some typical properties of large AND/OR Boolean formulas, Random Struct Algorithm 10 pp 337– (1997) · Zbl 0874.60011
[32] Marckert, The CRT is the scaling limit of unordered binary trees, Random Struct Algorithm (in press) · Zbl 1223.05027
[33] Meir, On the altitude of nodes in random trees, Can J Math 30 pp 997– (1978) · Zbl 0394.05015
[34] Milnor, Dynamics in one complex variable (1999) · Zbl 0946.30013
[35] Otter, The number of trees, Ann Math 49 pp 583– (1948) · Zbl 0032.12601
[36] Pólya, Kombinatorische Anzahlbestimmungen für Gruppen, Graphen und chemische Verbindungen, Acta Math 68 pp 145– (1937) · JFM 63.0547.04
[37] Pólya, Combinatorial enumeration of groups, graphs and chemical compounds (1987)
[38] Rényi, On the height of trees, Aust J Math 7 pp 497– (1967) · Zbl 0153.25802
[39] Riordan, Enumeration of trees by height and diameter, IBM J Res Dev 4 pp 473– (1960) · Zbl 0097.25201
[40] N. J. A. Sloane The on-line encyclopedia of integer sequences 2008 www.research.att.com/-njas/sequences/.AccessedonDecember5
[41] Szekeres, Combinatorial mathematics X, Lecture Notes in Mathematics pp 392– (1982)
[42] Whittaker, A course of modern analysis (1927)
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.