TY - JOUR
T1 - The distribution of the maximum protection number in simply generated trees
AU - Heuberger, Clemens
AU - Selkirk, Sarah J.
AU - Wagner, Stephan
N1 - Publisher Copyright:
© The Author(s), 2024. Published by Cambridge University Press.
PY - 2024
Y1 - 2024
N2 - The protection number of a vertex <![CDATA[ $v$ ]]> in a tree is the length of the shortest path from <![CDATA[ $v$ ]]> to any leaf contained in the maximal subtree where <![CDATA[ $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 <![CDATA[ $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.
AB - The protection number of a vertex <![CDATA[ $v$ ]]> in a tree is the length of the shortest path from <![CDATA[ $v$ ]]> to any leaf contained in the maximal subtree where <![CDATA[ $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 <![CDATA[ $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.
KW - generating functions
KW - Protection number
KW - simply generated trees
UR - http://www.scopus.com/inward/record.url?scp=85190549228&partnerID=8YFLogxK
U2 - 10.1017/S0963548324000099
DO - 10.1017/S0963548324000099
M3 - Article
AN - SCOPUS:85190549228
SN - 0963-5483
JO - Combinatorics Probability and Computing
JF - Combinatorics Probability and Computing
ER -