The CRT is the scaling limit of unordered binary trees

DOI10.1002/RSA.20332MaRDI QIDQ5198666zbMATH OpenOpenAlexFDO

Authors Jean-François Marckert, Grégory Miermont

Publication date 9 August 2011

Published in Random Structures \& Algorithms (Search for Journal in Brave)

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

zbMATH Keywords

CRTGromov HausdorffPólya treesunordered treesweak convergence

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80)

Abstract: We prove that a uniform, rooted unordered binary tree with $n$ vertices has the Brownian continuum random tree as its scaling limit for the Gromov-Hausdorff topology. The limit is thus, up to a constant factor, the same as that of uniform plane trees or labeled trees. Our analysis rests on a combinatorial and probabilistic study of appropriate trimming procedures of trees.

Recommendations

• The continuum random tree is the scaling limit of unlabeled unrooted trees
• Scaling limits of random trees and graphs
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• The continuum random tree. I
• Scaling limits of random Pólya trees

Cites work

• A course in metric geometry
• A limit theorem for the contour process of conditioned Galton-Watson trees
• Functionals of Brownian meander and Brownian excursion
• scientific article; zbMATH DE number 43570 (Why is no real title available?)
• scientific article; zbMATH DE number 1245556 (Why is no real title available?)
• scientific article; zbMATH DE number 3274494 (Why is no real title available?)
• Limit distributions and random trees derived from the birthday problem with unequal probabilities
• Probabilistic and fractal aspects of Lévy trees
• Rayleigh processes, real trees, and root growth with re-grafting
• Self-similar fragmentations
• Subtree prune and regraft: a reversible real tree-valued Markov process
• The continuum random tree. I
• The continuum random tree. III
• The depth first processes of Galton-Watson trees converge to the same Brownian excursion
• The exploration process of inhomogeneous continuum random trees, and an extension of Jeulin's local time identity
• The height of random binary unlabelled trees
• The number of trees
• The topological structure of scaling limits of large planar maps

Cited in

(20)

• Random enriched trees with applications to random graphs
• Scaling limits for some random trees constructed inhomogeneously
• Self-similar real trees defined as fixed points and their geometric properties
• Scaling limit of random forests with prescribed degree sequences
• Scaling limits of random Pólya trees
• Scaling limits of random trees and graphs
• Schröder's problems and scaling limits of random trees
• Scaling limits for a family of unrooted trees
• The distribution of height and diameter in random non-plane binary trees
• The CRT is the scaling limit of random dissections
• The degree profile of random Pólya trees
• Simply generated unrooted plane trees
• A view from the bridge spanning combinatorics and probability
• Graph limits of random graphs from a subset of connected k-trees
• Graphon convergence of random cographs
• Scaling Limits of Markov-Branching Trees and Applications
• Cutoff on trees is rare
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• The shape of unlabeled rooted random trees
• The gap between Gromov-Vague and Gromov-Hausdorff-vague topology

This page was built for publication: The CRT is the scaling limit of unordered binary trees

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