23 Jul 2026

Leonard Vetter (KIT, Institute for Operations Research)

Abstract: The goal of this talk is first to give a short introduction to Bienaymé trees (also known as Galton-Watson trees), which model the genealogy of a branching process. We then explore the asymptotic structure of large random trees, with the goal of counting rare subtrees. A Bienaymé tree is a random plane tree in which every vertex has a random number of children, drawn independently from a fixed offspring distribution. We take this distribution to be critical with finite variance, and condition the tree to have $n$ vertices. The goal is to approximate how often a given subtree appears as a general (also known as non-fringe) subtree inside it as $n\to\infty$. Fix a sequence of plane trees $(T_k)$ with $|T_k|=k$, and let $k=k_n$ grow with $n$. We show that if $k_n$ is subpolynomial in $n$ and the probability that $T_{k_n}$ appears as a non-fringe subtree in the unconditioned tree is $O(1/n)$, then the number of its occurrences is asymptotically Poisson, provided a condition that controls the possible overlap between nearby occurrences. The main tool is the Chen-Stein method, applied to the integer-valued path that encodes the plane tree.