Premium
Distances between pairs of vertices and vertical profile in conditioned Galton–Watson trees
Author(s) -
Devroye Luc,
Janson Svante
Publication year - 2011
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20319
Subject(s) - mathematics , excursion , combinatorics , watson , mathematical proof , conjecture , tree (set theory) , geometry , computer science , political science , law , natural language processing
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 (Bousquet‐Mélou and Janson, Ann Appl Probab 16 (2006) 1597–1632), 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). © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 381–395, 2011