Distances between pairs of vertices and vertical profile in conditioned Galton--Watson trees

Simple item page
dc.creatorDevroye, Luc
dc.creatorJanson, Svante
dc.date2008-12-17
dc.date.accessioned2026-07-07T12:16:16Z
dc.date.available2026-07-07T12:16:16Z
dc.descriptionWe 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 second proof yields a more general estimate for generating functions, which is used to prove a conjecture by Bousquet-Melou and Janson 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).
dc.description16 pages
dc.identifierhttps://arxiv.org/abs/0812.3326
dc.identifierhttp://arxiv.org/abs/0812.3326
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/211751
dc.subjectProbability
dc.subjectCombinatorics
dc.subject60C05; 05C05
dc.titleDistances between pairs of vertices and vertical profile in conditioned Galton--Watson trees
dc.typetext

Files

Collections

arXiv