Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2021
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2106.14389 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
Table of Contents:
- We study several parameters of a random Bienaymé-Galton-Watson tree $T_n$ of size $n$ defined in terms of an offspring distribution $ξ$ with mean $1$ and nonzero finite variance $σ^2$. Let $f(s)={\bf E}\{s^ξ\}$ be the generating function of the random variable $ξ$. We show that the independence number is in probability asymptotic to $qn$, where $q$ is the unique solution to $q = f(1-q)$. One of the many algorithms for finding the largest independent set of nodes uses a notion of repeated peeling away of all leaves and their parents. The number of rounds of peeling is shown to be in probability asymptotic to $\log n / \log\bigl(1/f'(1-q)\bigr)$. Finally, we study a related parameter which we call the leaf-height. Also sometimes called the protection number, this is the maximal shortest path length between any node and a leaf in its subtree. If $p_1 = {\bf P}\{ξ=1\}>0$, then we show that the maximum leaf-height over all nodes in $T_n$ is in probability asymptotic to $\log n/\log(1/p_1)$. If $p_1 = 0$ and $κ$ is the first integer $i>1$ with ${\bf P}\{ξ=i\}>0$, then the leaf-height is in probability asymptotic to $\log_κ\log n$.