Center for Applied Mathematical Sciences Visit USC
USC Donrsife Homepage
Sep 12
3:30 PM - 4:30 PM KAP 414
Self-similarity of random trees and applications
Ilia Zaliapin University of Nevada-Reno

Hierarchical branching organization is ubiquitous in nature. It is readily seen in river basins, drainage networks, bronchial passages, botanical trees, lightening, and snowflakes, to mention but a few. Empirical evidence reveals a surprising similarity among various natural hierarchies – many of them are closely approximated by so-called self-similar trees (SSTs). The Horton and Tokunaga branching laws provide a flexible framework for studying self-similarity in random trees. The Horton self-similarity is a weaker property that addresses the principal branching in a tree; it is a counterpart of the power-law size distribution for elements of a branching system. The stronger Tokunaga self-similarity addresses so-called side branching; it ensures that different levels of a hierarchy have the same probabilistic structure (in a sense to be defined). The Horton and Tokunaga self-similarity have been empirically established in numerous observed and modeled systems, including river networks, vein structure of botanical leaves, diffusion limited aggregation, two dimensional site percolation, and nearest-neighbor clustering in Euclidean spaces. The diversity of these processes and models hints at the existence of a universal underlying mechanism responsible for the Tokunaga self-similarity and prompts the question: What basic probability models can generate Tokunaga self-similar trees with a range of parameters? We review the existing results on self-similarity for the critical binary Galton-Watson tree and present recent findings on self-similarity for tree representation of coalescent processes, random walks, and white noises. In particular, we establish the equivalence of tree representation for selected coalescent processes and time series models. The presented results suggest at least a partial explanation for the omnipresence of Tokunaga self-similar structures in natural branching systems. The results are illustrated using applications in hydrology, seismology, and billiard dynamics.

Previous colloquium: Learning Social Similarities from Friendship Patterns Next colloquium: Poincaré and the early history of 3-manifolds