×

zbMATH — the first resource for mathematics

Distances between pairs of vertices and vertical profile in conditioned Galton-Watson trees. (English) Zbl 1223.05049
Summary: We consider a conditioned Galton–Watson tree and prove an estimate of the number of pairs of vertices with a given distance, or, equivalently, the number of paths of a given length.
We give two proofs of this result, one probabilistic and the other using generating functions and singularity analysis.
Moreover, the latter proof yields a more general estimate for generating functions, which is used to prove a conjecture by Bousquet-Mélou and Janson [M. Bousquet-Mélou and S. Janson, Ann. Appl. Probab. 16, No. 3, 1597–1632 (2006; Zbl 1132.60009)], saying that the vertical profile of a randomly labelled conditioned Galton–Watson tree converges in distribution, after suitable normalization, to the density of ISE (Integrated Superbrownian Excursion).

MSC:
05C12 Distance in graphs
05C05 Trees
05C38 Paths and cycles
68W40 Analysis of algorithms
Citations:
Zbl 1132.60009
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Aldous, Stochastic Analysis (Proc., Durham, 1990), London Math Soc Lecture Note Ser 167 pp 23– (1991)
[2] Aldous, Asymptotic fringe distributions for general families of random trees, Ann Appl Probab 1 pp 228– (1991) · Zbl 0733.60016
[3] Aldous, Tree-based models for random distribution of mass, J Stat Phys 73 pp 625– (1993) · Zbl 1102.60318
[4] Bousquet-Mélou, Limit laws for embedded trees. Applications to the integrated super-Brownian excursion, Random Struct Algorithms 29 pp 475– (2006) · Zbl 1107.60302
[5] Bousquet-Mélou, The density of the ISE and local limit laws for embedded trees, Ann Appl Probab 16 pp 1597– (2006) · Zbl 1132.60009
[6] Devroye, Probabilistic Methods for Algorithmic Discrete Mathematics, Algorithms Combin 16 pp 249– (1998)
[7] Drmota, The width of Galton-Watson trees conditioned by the size, Discrete Math Theor Comput Sci 6 pp 387– (2004)
[8] Dwass, The total progeny in a branching process and a related random walk, J Appl Probab 6 pp 682– (1969) · Zbl 0192.54401
[9] Flajolet, Analytic Combinatorics (2008)
[10] Janson, Random cutting and records in deterministic and random trees, Random Struct Algorithm 29 pp 139– (2006) · Zbl 1120.05083
[11] Janson, Proceedings of Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Probabilities (Nancy, France, 2006) pp 331– (2006)
[12] Kolchin, Random mappings (1986)
[13] Meir, On the altitude of nodes in random trees, Can J Math 30 pp 997– (1978) · Zbl 0394.05015
[14] Pitman, DIMACS Series of Discrete Mathematics Theoretical Computer Science, 41, in: Microsurveys in Discrete Probability (Princeton, NJ, 1997) pp 163– (1998)
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.