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

branching processesrandom treesrandom recursive trees\(m\)-ary search treescladesextended fringe treesfragmentation treesfringe treespreferential attachment treesprotected nodes

Mathematics Subject Classification ID

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

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

(28)

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

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)