On the independence number of some random trees (Q2201542)

This paper studies the independence number of some random trees. Let \(T_n\) be random trees that can be defined as stopped family trees of Crump-Mode-Jagers processes for some point process \(\xi_i\) and weight \(\psi\). Let \(I(T_n)\) be the corresponding independent number. As \(n\) tends to infinity, it is shown that \(I(T_n)/|T_n|\) tends to a constant \(\alpha\int_0^{\infty}e^{-\alpha t}p(t)dt\), which does not rely on \(\psi\). Here, \(\alpha\) is the Malthusian parameter and \(p(t)\) is the unique function \([0,\infty)\rightarrow (0,1]\) defined by \(p(t)=\mathbb{E}\prod_{i:\xi_i\le t}(1-p(t-\xi_i))\). This type of results have been worked out for random recursive trees, binary and \(m\)-ary search trees, preferential attachment trees in this work.