The distance to the border of a random tree

arXiv2205.10645MaRDI QIDQ6399787FDOQ6399787

Authors: Víctor J. Maciá 

Publication date: 21 May 2022

Abstract: Given a Galton-Watson process conditioned to have total progeny equal to $n$, we study the asymptotic probability that this conditioned Galton-Watson process has distance to the border bigger or equal than $k$, as the number of nodes $nightarrowinfty$. A problem which is akin to this one was solved by R'enyi and Szekeres for Cayley trees, de Bruijn, Knuth, and Rice for plane trees and Flajolet, Gao, Odlyzko, and Richmond for binary trees. The distance to the border is dual, in a certain sense, to the height. The first of these distances is the minimum of the distances from the root to the leaves. The second is the maximum of the distances from the root to the leaves. These are two extreme complementary cases.

Mathematics Subject Classification ID

Trees (05C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Asymptotic enumeration (05A16) Iteration of holomorphic maps, fixed points of holomorphic maps and related problems for several complex variables (32H50)

This page was built for publication: The distance to the border of a random tree

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6399787)