Extremal properties of random trees
arXiv:cond-mat/0105309 · doi:10.1103/PhysRevE.64.035101
Abstract
We investigate extremal statistical properties such as the maximal and the minimal heights of randomly generated binary trees. By analyzing the master evolution equations we show that the cumulative distribution of extremal heights approaches a traveling wave form. The wave front in the minimal case is governed by the small-extremal-height tail of the distribution, and conversely, the front in the maximal case is governed by the large-extremal-height tail of the distribution. We determine several statistical characteristics of the extremal height distribution analytically. In particular, the expected minimal and maximal heights grow logarithmically with the tree size, N, hmin ~ vmin ln N, and hmax ~ vmax ln N, with vmin=0.373365 and vmax=4.31107, respectively. Corrections to this asymptotic behavior are of order O(ln ln N).
4 pages, revtex
References in corpus (8)
- Shift in the velocity of a front due to a cut-off
- Front propagation into unstable states: Universal algebraic convergence towards uniformly translating pulled fronts
- Unified View of Scaling Laws for River Networks
- Largest Lyapunov Exponent for Many Particle Systems at Low Densities
- Universal algebraic relaxation of fronts propagating into an unstable state
- Traveling Waves, Front Selection, and Exact Nontrivial Exponents in a Random Fragmentation Problem
- Fragmentation with a Steady Source
- The branching structure of diffusion-limited aggregates
Cited by in corpus (25)
- Scale-Free Networks are Ultrasmall
- Extreme value statistics of correlated random variables: a pedagogical review
- Random Convex Hulls and Extreme Value Statistics
- Extreme Value Statistics and Traveling Fronts: An Application to Computer Science
- Extreme Value Statistics and Traveling Fronts: Various Applications
- The power of choice in network growth
- Shattering Transitions in Collision-Induced Fragmentation
- Exact Solution of a Field Theory Model of Frontal Photopolymerization
- Dynamics of Social Diversity
- Traveling Front Solutions to Directed Diffusion Limited Aggregation, Digital Search Trees and the Lempel-Ziv Data Compression Algorithm
- Addition-Deletion Networks
- On The Structure of Competitive Societies
- Extreme value statistics and return intervals in long-range correlated uniform deviates
- Random walks and diameter of finite scale-free networks
- Growing network with j-redirection
- Leadership Statistics in Random Structures
- On the topological classification of binary trees using the Horton-Strahler index
- Condensates in Driven Aggregation Processes
- Persistence of Random Walk Records
- Fragmentation of Random Trees
- Activity ageing in growing networks
- Dynamical barriers for the random ferromagnetic Ising model on the Cayley tree : traveling-wave solution of the real space renormalization flow
- Fluctuating Fronts as Correlated Extreme Value Problems: An Example of Gaussian Statistics
- Statistics of Partial Minima
- Continuum Cascade Model of Directed Random Graphs: Traveling Wave Analysis