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

DOI10.1214/16-PS272zbMath1406.60120arXiv1601.03691OpenAlexW2962939975MaRDI QIDQ521300

Svante Janson, Cecilia Holmgren

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Related Items (24)

Multivariate normal limit laws for the numbers of fringe subtrees in \(m\)-ary search trees and preferential attachment trees ⋮ Tree limits and limits of random trees ⋮ Central limit theorems for additive functionals and fringe trees in tries ⋮ ON SEVERAL PROPERTIES OF A CLASS OF PREFERENTIAL ATTACHMENT TREES—PLANE-ORIENTED RECURSIVE TREES ⋮ Condensation phenomena in preferential attachment trees with neighbourhood influence ⋮ Renewal theory for iterated perturbed random walks on a general branching process tree: intermediate generations ⋮ Local weak convergence for PageRank ⋮ 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 ⋮ On the independence number of some random trees ⋮ The existence of a giant cluster for percolation on large Crump–Mode–Jagers trees ⋮ The fluctuations of the giant cluster for percolation on random split trees ⋮ Metric dimension of critical Galton-Watson trees and linear preferential attachment trees ⋮ Local convergence for permutations and local limits for uniform \(\rho \)-avoiding permutations with \(|\rho |=3\) ⋮ Random Recursive Trees and Preferential Attachment Trees are Random Split Trees ⋮ Limiting probabilities for vertices of a given rank in 1-2 trees ⋮ 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