The height of discrete-time critical beta-splitting trees

Source abstract

We determine the first-order asymptotic height of the discrete-time critical beta-splitting tree. If $L_n^*$ denotes the height (maximum root-to-leaf graph distance) of the tree with $n$ leaves, then $$\frac{L_n^*}{(\log n)^2} \longrightarrow C_{\mathrm{ht}}:=\min_{θ>1} \fracθ{2\{ψ(θ)+γ\}} \approx 0.976$$ almost surely and in $L^{p}$ for every fixed $p>1$ as $n \to \infty$. Here $ψ$ is the digamma function and $γ$ is Euler's constant. This answers \cite[Open Problem~4]{AldousJansonII} of Aldous and Janson~.