Scaling limits of k-ary growing trees

DOI10.1214/14-AIHP622MaRDI QIDQ902873zbMATH OpenFDO

Authors Bénédicte Haas, Robin Stephenson

Publication date 4 January 2016

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

Full work available at URL https://arxiv.org/abs/1402.1084, https://projecteuclid.org/euclid.aihp/1445432044

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)

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.

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

Cites work

• scientific article; zbMATH DE number 1713116 (Why is no real title available?)
• scientific article; zbMATH DE number 19286 (Why is no real title available?)
• scientific article; zbMATH DE number 2046067 (Why is no real title available?)
• scientific article; zbMATH DE number 1859371 (Why is no real title available?)
• scientific article; zbMATH DE number 1409903 (Why is no real title available?)
• scientific article; zbMATH DE number 3232102 (Why is no real title available?)
• A new family of Markov branching trees: the alpha-gamma model
• A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces
• Branching processes in Lévy processes: The exploration process
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Continuum tree asymptotics of discrete fragmentations and applications to phylogenetic mod\-els
• General fragmentation trees
• Homogeneous fragmentation processes
• Probabilistic and fractal aspects of Lévy trees
• 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.
• Random Fragmentation and Coagulation Processes
• Random real trees
• Random trees and general branching processes
• Rayleigh processes, real trees, and root growth with re-grafting
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• Self-similar fragmentations
• Self-similar scaling limits of non-increasing Markov chains
• Spinal partitions and invariance under re-rooting of continuum random trees
• The continuum random tree. III
• The genealogy of self-similar fragmentations with negative index as a continuum random tree
• The stable trees are nested
• The two-parameter Poisson-Dirichlet distribution derived from a stable subordinator

Cited in

(18)

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

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)