Random self-similar trees: a mathematical theory of Horton laws

DOI10.1214/19-PS331zbMATH Open1434.05037arXiv1905.02629MaRDI QIDQ2305573FDOQ2305573

Authors: Ilya Zaliapin, Yevgeniy Kovchegov 

Publication date: 11 March 2020

Published in: Probability Surveys (Search for Journal in Brave)

Abstract: The Horton laws originated in hydrology with a 1945 paper by Robert E. Horton, and for a long time remained a purely empirical finding. Ubiquitous in hierarchical branching systems, the Horton laws have been rediscovered in many disciplines ranging from geomorphology to genetics to computer science. Attempts to build a mathematical foundation behind the Horton laws during the 1990s revealed their close connection to the operation of pruning -- erasing a tree from the leaves down to the root. This survey synthesizes recent results on invariances and self-similarities of tree measures under various forms of pruning. We argue that pruning is an indispensable instrument for describing branching structures and representing a variety of coalescent and annihilation dynamics. The Horton laws appear as a characteristic imprint of self-similarity, which settles some questions prompted by geophysical data.

Full work available at URL: https://arxiv.org/abs/1905.02629

Recommendations

• Horton law in self-similar trees
• Tokunaga and Horton self-similarity for level set trees of Markov chains
• A self-similar invariance of critical binary Galton-Watson trees
• Horton self-similarity of Kingman's coalescent tree
• Entropy rates for Horton self-similar trees

zbMATH Keywords

Horton lawshydrophysics

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Brownian motion (60J65) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Hydrodynamic stability (76E99)

Cites Work

• Entropy rates for Horton self-similar trees
• Title not available (Why is that?)
• Cross-Multiplicative Coalescent Processes and Applications
• Computational topology. An introduction
• Title not available (Why is that?)
• A Mathematical Theory of Communication
• The coalescent
• Title not available (Why is that?)
• Title not available (Why is that?)
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Random Trees
• Title not available (Why is that?)
• Morse Theory. (AM-51)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Selected Topics in Characteristic Functions
• Random Fragmentation and Coagulation Processes
• Differential equation approximations for Markov chains
• Growth of Lévy trees
• On programming of arithmetic operations
• Title not available (Why is that?)
• Weighted Occupation Time for Branching Particle Systems and a Representation for the Supercritical Superprocess
• Title not available (Why is that?)
• On Hilbert's thirteenth problem and related questions
• The prolific backbone for supercritical superprocesses
• Quasi-stationary distributions. Markov chains, diffusions and dynamical systems.
• A kinetic view of statistical physics
• Stochastic models for fractional calculus
• Recent progress in coalescent theory.
• Register Allocation for Unary–Binary Trees
• A note on the Horton-Strahler number for random trees
• Some width function asymptotics for weighted trees
• Statistics of shocks in solutions of inviscid Burgers equation
• Functionals of Brownian meander and Brownian excursion
• Deterministic and stochastic models for coalescence (aggregation and coagulation): A review of the mean-field theory for probabilists
• The continuum random tree. III
• Williams' decomposition of the Lévy continuum random tree and simultaneous extinction probability for populations with neutral mutations
• Construction of Markovian coalescents
• La théorie générale de la mesure dans son application à l'étude des systèmes dynamiques de la mécanique non linéaire
• Path Decomposition and Continuity of Local Time for One-Dimensional Diffusions, I
• Title not available (Why is that?)
• An invitation to Morse theory
• The continuum random tree. I
• Topological classification of Morse functions and generalisations of Hilbert's 16-th problem
• The inviscid Burgers equation with initial data of Brownian type
• Ballistic annihilation and deterministic surface growth.
• Title not available (Why is that?)
• Models of fractal river basins
• First Passage and Recurrence Distributions
• Rayleigh processes, real trees, and root growth with re-grafting
• Smoluchowski's coagulation equation: Uniqueness, nonuniqueness and a hydrodynamic limit for the stochastic coalescent
• Genealogy of shocks in Burgers turbulence with white noise initial velocity
• Branching processes in Lévy processes: The exploration process
• Title not available (Why is that?)
• The \(\Lambda \)-coalescent speed of coming down from infinity
• Title not available (Why is that?)
• Tree-valued Markov chains derived from Galton-Watson processes
• Branching processes in Lévy processes: Laplace functionals of snakes and superprocesses
• Title not available (Why is that?)
• Pruning Galton-Watson trees and tree-valued Markov processes
• The inviscid Burgers equation with Brownian initial velocity
• Ordered additive coalescent and fragmentations associated to Lévy processes with no positive jumps
• Title not available (Why is that?)
• Probability and real trees. Ecole d'Eté de Probabilités de Saint-Flour XXXV -- 2005. Lecture given at the Saint-Flour probability summer school, July 6--23, 2005.
• An introduction to measure theory
• On weighted heights of random trees
• The average number of registers needed to evaluate a binary tree optimally
• The number of registers required for evaluating arithmetic expressions
• Moment of degeneration of a branching process and height of a random tree
• Smooth functions statistics
• Clustering statistics for sticky particles with Brownian initial velocity
• Title not available (Why is that?)
• The height of increasing trees
• Note on a one-dimensional system of annihilating particles
• Sur un Théorème de Maximum de Mm. Hardy et Littlewood
• On some annihilating and coalescing systems
• Last exit decompositions and regularity at the boundary of transition probabilities
• Singularities and the distribution of density in the Burgers/adhesion model
• Tokunaga and Horton self-similarity for level set trees of Markov chains
• Spines, skeletons and the strong law of large numbers for superdiffusions
• Horton-Strahler ordering of random binary trees
• The uniform random tree in a Brownian excursion
• A self-similar invariance of critical binary Galton-Watson trees
• Random self-similar trees and a hierarchical branching process
• The register function for t -ary trees
• Title not available (Why is that?)
• Self-similarity of the branching structure in very large DLA clusters and other branching fractals
• A Large Deviation Rate and Central Limit Theorem for Horton Ratios
• Reductions of binary trees and lattice paths induced by the register function
• A unified approach to the analysis of Horton‐Strahler parameters of binary tree structures
• Horton self-similarity of Kingman's coalescent tree
• Horton law in self-similar trees
• Fractal Trees with Side Branching
• Tokunaga self-similarity arises naturally from time invariance
• Hereditary tree growth and Lévy forests
• Two scales in asynchronous ballistic annihilation
• Tree-dependent extreme values: the exponential case
• Central limit theorem for the Horton–Strahler bifurcation ratio of general branch order

Cited In (12)

• Large Deviation Theorem for Branches of the Random Binary Tree in the Horton--Strahler Analysis
• Invariant Galton–Watson trees: metric properties and attraction with respect to generalized dynamical pruning
• Fractal trees and Horton's laws
• Dynamical pruning of rooted trees with applications to 1-D ballistic annihilation
• The Horton-Strahler number of conditioned Galton-Watson trees
• Asymptotic pressure on some self-similar trees
• Invariance and attraction properties of Galton-Watson trees
• Self-similarity and spectral asymptotics for the continuum random tree
• Title not available (Why is that?)
• Inevitable self-similar topology of binary trees and their diverse hierarchical density
• Tokunaga and Horton self-similarity for level set trees of Markov chains
• A Hierarchical Cluster System Based on Horton–Strahler Rules for River Networks

This page was built for publication: Random self-similar trees: a mathematical theory of Horton laws

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2305573)