1 results
The distribution of the maximum protection number in simply generated trees
- Part of
-
- Journal:
- Combinatorics, Probability and Computing / Volume 33 / Issue 4 / July 2024
- Published online by Cambridge University Press:
- 12 April 2024, pp. 518-553
-
- Article
-
- You have access
- Open access
- HTML
- Export citation
-
The protection number of a vertex
$v$ in a tree is the length of the shortest path from 
$v$ to any leaf contained in the maximal subtree where 
$v$ is the root. In this paper, we determine the distribution of the maximum protection number of a vertex in simply generated trees, thereby refining a recent result of Devroye, Goh, and Zhao. Two different cases can be observed: if the given family of trees allows vertices of outdegree 
$1$, then the maximum protection number is on average logarithmic in the tree size, with a discrete double-exponential limiting distribution. If no such vertices are allowed, the maximum protection number is doubly logarithmic in the tree size and concentrated on at most two values. These results are obtained by studying the singular behaviour of the generating functions of trees with bounded protection number. While a general distributional result by Prodinger and Wagner can be used in the first case, we prove a variant of that result in the second case.
