Scaling limits of k-ary growing trees

2014/02/05 by Haas, Bénédicte, Stephenson, Robin
#FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1402.1084

Abstract

For each integer k ≥ 2, we introduce a sequence of k-ary discrete trees constructed recursively by choosing at each step an edge uniformly among the present edges and grafting on "its middle" k-1 new edges. When k=2, this corresponds to a well-known algorithm which was first introduced by Rémy. Our main result concerns the asymptotic behavior of these trees as n becomes large: for all k, the sequence of k-ary trees grows at speed n^1/k towards a k-ary random real tree that belongs to the family of self-similar fragmentation trees. This convergence is proved with respect to the Gromov-Hausdorff-Prokhorov topology. We also study embeddings of the limiting trees when k varies.

Related

• Scaling limits for some random trees constructed inhomogeneously
• Growing random graphs with a preferential attachment structure
• Scaling limit of random forests with prescribed degree sequences
• Rayleigh processes, real trees, and root growth with re-grafting
• The CRT is the scaling limit of unordered binary trees