Scaling limits of k-ary growing trees

DOI10.1214/14-AIHP622zbMATH Open1329.60076arXiv1402.1084MaRDI QIDQ902873FDOQ902873

Robin Stephenson, Bénédicte Haas

Publication date: 4 January 2016

Published in: Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Abstract: For each integer $kgeq2$, 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'emy. 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.

Full work available at URL: https://arxiv.org/abs/1402.1084

Recommendations

• Scaling limit of random \(k\)-trees
• Scaling limits of random trees and random graphs
• Scaling limits of random trees and graphs
• Scaling limits of random Pólya trees
• Scaling limits for a family of unrooted trees
• Scaling limits for some random trees constructed inhomogeneously
• Scaling limits of slim and fat trees
• Scaling Limits of Markov-Branching Trees and Applications
• The scaling limit of lattice trees in high dimensions
• Scaling limits of random trees and planar maps

zbMATH Keywords

scaling limitsGromov-Hausdorff-Prokhorov topologyrandom growing treesself-similar fragmentation trees

Mathematics Subject Classification ID

Functional limit theorems; invariance principles (60F17) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic mod\-els
• The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Random Fragmentation and Coagulation Processes
• Self-similar fragmentations
• Probabilistic and fractal aspects of Lévy trees
• Title not available (Why is that?)
• Homogeneous fragmentation processes
• The continuum random tree. III
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• Rayleigh processes, real trees, and root growth with re-grafting
• A new family of Markov branching trees: the alpha-gamma model
• The genealogy of self-similar fragmentations with negative index as a continuum random tree
• Spinal partitions and invariance under re-rooting of continuum random trees
• Branching processes in Lévy processes: The exploration process
• Random real trees
• Title not available (Why is that?)
• A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces
• General fragmentation trees
• The stable trees are nested
• Random trees and general branching processes
• Title not available (Why is that?)
• Probability and real trees. Ecole d'Eté de Probabilités de Saint-Flour XXXV -- 2005. Lecture given at the Saint-Flour probability summer school, July 6--23, 2005.
• Self-similar scaling limits of non-increasing Markov chains
• Title not available (Why is that?)

Cited In (17)

• Local limit of labeled trees and expected volume growth in a random quadrangulation
• Limits of random tree-like discrete structures
• Scaling limits for a family of unrooted trees
• Geometry of weighted recursive and affine preferential attachment trees
• Bivariate Markov chains converging to Lamperti transform Markov additive processes
• Scaling Limits of Markov-Branching Trees and Applications
• A scaling limit for the cover time of the binary tree
• Growing random uniform \(d\)-ary trees
• Scaling limits of multi-type Markov branching trees
• Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set
• Tail asymptotics for extinction times of self-similar fragmentations
• On the asymptotic growth rate of some spanning trees embedded in \(\mathbb R^d\)
• The growth rate of high-dimensional tree polycubes
• Scaling limits for some random trees constructed inhomogeneously
• Growing random graphs with a preferential attachment structure
• Random enriched trees with applications to random graphs
• The scaling limit of lattice trees in high dimensions

This page was built for publication: Scaling limits of \(k\)-ary growing trees

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