Invariance and attraction properties of Galton-Watson trees

2019/11/19 by Kovchegov, Yevgeniy, Zaliapin, Ilya
#60C05 #60J80 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1911.08095

Abstract

We give a description of invariants and attractors of the critical and subcritical Galton-Watson tree measures under the operation of Horton pruning (cutting tree leaves with subsequent series reduction). Under a regularity condition, the class of invariant measures consists of the critical binary Galton-Watson tree and a one-parameter family of critical Galton-Watson trees with offspring distribution \q_k\ that has a power tail q_k∼ Ck^-(1+1/q₀), where q₀∈(1/2,1). Each invariant measure has a non-empty domain of attraction under consecutive Horton pruning, specified by the tail behavior of the initial Galton-Watson offspring distribution. The invariant measures satisfy the Toeplitz property for the Tokunaga coefficients and obey the Horton law with exponent R = (1-q₀)^-1/q₀.

Related

• Invariant Galton-Watson trees: metric properties and attraction with respect to generalized dynamical pruning
• Invariance principles for pruning processes of Galton-Watson trees
• The Horton-Strahler number of Galton-Watson trees with possibly infinite variance
• Convergence of the pruning processes of stable Galton-Watson trees
• The Horton-Strahler Number of Conditioned Galton-Watson Trees