Fringe trees, Crump-Mode-Jagers branching processes and m-ary search trees

DOI10.1214/16-PS272MaRDI QIDQ521300zbMATH OpenOpenAlexFDO

Authors Cecilia Holmgren, Svante Janson

Publication date 7 April 2017

Published in Probability Surveys (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1601.03691, https://projecteuclid.org/euclid.ps/1490169611

zbMATH Keywords

\(m\)-ary search treesbranching processescladesextended fringe treesfragmentation treesfringe treespreferential attachment treesprotected nodesrandom recursive treesrandom trees

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80) Applications of branching processes (60J85) Data structures (68P05) Searching and sorting (68P10)

Abstract: This survey studies asymptotics of random fringe trees and extended fringe trees in random trees that can be constructed as family trees of a Crump-Mode-Jagers branching process, stopped at a suitable time. This includes random recursive trees, preferential attachment trees, fragmentation trees, binary search trees and (more generally) $m$-ary search trees, as well as some other classes of random trees. We begin with general results, mainly due to Aldous (1991) and Jagers and Nerman (1984). The general results are applied to fringe trees and extended fringe trees for several particular types of random trees, where the theory is developed in detail. In particular, we consider fringe trees of $m$-ary search trees in detail; this seems to be new. Various applications are given, including degree distribution, protected nodes and maximal clades for various types of random trees. Again, we emphasise results for $m$-ary search trees, and give for example new results on protected nodes in $m$-ary search trees. A separate section surveys results on height, saturation level, typical depth and total path length, due to Devroye (1986), Biggins (1995, 1997) and others. This survey contains well-known basic results together with some additional general results as well as many new examples and applications for various classes of random trees.

Recommendations

• Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees
• Protected nodes and fringe subtrees in some random trees
• Asymptotic fringe distributions for general families of random trees
• On the height of random m‐ary search trees
• Using Pólya urns to show normal limit laws for fringe subtrees in \(m\)-ary search trees

Cited in

(37)

• Metric dimension of critical Galton-Watson trees and linear preferential attachment trees
• Central limit theorems for additive functionals and fringe trees in tries
• Condensation phenomena in preferential attachment trees with neighbourhood influence
• Local weak convergence for PageRank
• On the independence number of some random trees
• Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\)
• Limiting probabilities for vertices of a given rank in 1-2 trees
• Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees
• The existence of a giant cluster for percolation on large Crump–Mode–Jagers trees
• ON SEVERAL PROPERTIES OF A CLASS OF PREFERENTIAL ATTACHMENT TREES—PLANE-ORIENTED RECURSIVE TREES
• Renewal theory for iterated perturbed random walks on a general branching process tree: intermediate generations
• The fluctuations of the giant cluster for percolation on random split trees
• Random recursive trees and preferential attachment trees are random split trees
• Fragmentation process, pruning poset for rooted forests, and M\"obius inversion
• Tree limits and limits of random trees
• Sharp bound on the truncated metric dimension of trees
• Distributions of cherries and pitchforks for the Ford model
• A model for an epidemic with contact tracing and cluster isolation, and a detection paradox
• Random matrices and random graphs
• Degree distributions in recursive trees with fitnesses
• On several properties of a class of hybrid recursive trees
• Degree centrality and root finding in growing random networks
• Fluctuation bounds for continuous time branching processes and evolution of growing trees with a change point
• Models of random subtrees of a graph
• Asymptotic fluctuations in supercritical Crump-Mode-Jagers processes
• Voronoi cells in random split trees
• On a sufficient condition for explosion in CMJ branching processes and applications to recursive trees
• Random planar trees and the Jacobian conjecture
• Fringe trees for random trees with given vertex degrees
• Network evolution with mesoscopic delays
• Parking on trees with a (random) given degree sequence and the frozen configuration model
• A law of the iterated logarithm for iterated random walks, with application to random recursive trees
• Local weak limit of preferential attachment random trees with additive fitness
• The harmonic descent chain
• Fixation of leadership in non-Markovian growth processes
• Uncovering a graph
• A decorated tree approach to random permutations in substitution-closed classes

This page was built for publication: Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees

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