The CRT is the scaling limit of unordered binary trees

2009/02/26 by Marckert, Jean-François, Grégory Miermont, Miermont, Grégory · 1 citation
Mathematics · Physics and Astronomy · #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #Random Matrices and Applications

paper · doi:10.48550/arxiv.0902.4570

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.

Cited by

• The Shape of Unlabeled Rooted Random Trees

Related

• The continuum random tree is the scaling limit of unlabelled unrooted trees
• The GHP scaling limit of uniform spanning trees in high dimensions
• Rayleigh processes, real trees, and root growth with re-grafting
• Scaling limit of the Aldous-Broder chain on regular graphs: the transient regime
• The scaling limit of the minimum spanning tree of the complete graph