The Horton-Strahler number of Galton-Watson trees with possibly infinite variance

Abstract

The Horton-Strahler number, also known as the register function, provides a tool for quantifying the branching complexity of a rooted tree. We consider the Horton-Strahler number of critical Galton-Watson trees conditioned to have size $n$ and whose offspring distribution is in the domain of attraction of an $\alpha$-stable law with $\alpha \in [1,2]$. We give tail estimates and when $\alpha \ne 1$, we prove that it grows as $\frac{1}{\alpha }{\log }_{\alpha /(\alpha -1)}n$ in probability. This extends the result in Brandenberger, Devroye \& Reddad [6] dealing with the finite variance case for which $\alpha =2$. We also characterize the cases where $\alpha =1$, namely the spectrally positive Cauchy regime, which exhibits more complex behaviors. Our proofs are new and probabilistic; they relate the Horton-Strahler number with other shape parameters such as the height or largest degree.

33 pages, 1 figure. Version to appear in the Annals of Applied Probability