The Horton-Strahler Number of Conditioned Galton-Watson Trees

2020/10/16 by Brandenberger, Anna M., Devroye, Luc, Reddad, Tommy · 1 citation
#05C05 (Secondary) #60C05 #60J80 (Primary) 05C80 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.2010.08613

Abstract

The Horton-Strahler number of a tree is a measure of its branching complexity; it is also known in the literature as the register function. We show that for critical Galton-Watson trees with finite variance conditioned to be of size n, the Horton-Strahler number grows as (1)/(2)log₂ n in probability. We further define some generalizations of this number. Among these are the rigid Horton-Strahler number and the k-ary register function, for which we prove asymptotic results analogous to the standard case.

Cited by

• The Horton-Strahler number of butterfly trees

Related

• The Horton-Strahler number of Galton-Watson trees with possibly infinite variance
• Fluctuations of the Horton-Strahler number of stable Galton-Watson trees
• The Horton-Strahler number of butterfly trees
• Scaling limits of Markov branching trees and Galton-Watson trees\n conditioned on the number of vertices with out-degree in a given set
• Invariance and attraction properties of Galton-Watson trees