The Horton-Strahler number of conditioned Galton-Watson trees (Q2243907)

The authors compute the asymptotics of the Horton-Strahler number for critical Galton-Watson trees whose offspring distribution has finite variance, conditioned to have \(n\) vertices, as \(n\to\infty\). The Horton-Strahler number \(H(T)\) -- or register function -- of a rooted tree \(T\) is defined recursively: \begin{itemize} \item a number \(0\) (or \(1\) in the computer science literature) is assigned to each leaf; \item a node with \(k\geq 1\) children having Horton--Strahler numbers \(H_1 \geq H_2 \geq \dots\geq H_k\) is assigned the number \(H_1 + 1_{\{H_1=H_2\}}\); \item \(H(T)\) is defined as the number assigned to the root. \end{itemize} The main result is that if \(T_n\) is a critical Galton-Watson tree whose offspring distribution has finite variance, then \(H(T_n) \sim \frac{1}{2}\log_2(n)\) in probability. This approach extends the results that were obtained in previous works for uniform plane binary trees to other classes of random trees -- for instance, to uniform (plane or non-plane) trees with \(n\) vertices. The main ingredients of the proofs are (a) the local limit of Galton-Watson trees (Kesten's tree), (b) estimates of the tail probability distribution of the Horton-Strahler number of an unconditioned Galton-Watson tree, and (c) the random walk view of a Galton-Watson tree (via its Lukasiewicz encoding) and rotationally invariant events. Finally, generalizations of the Horton-Strahler number are considered, using different recursive rules in their definitions, and studied using similar techniques.