Premium
The CRT is the scaling limit of unordered binary trees
Author(s) -
Marckert JeanFrançois,
Miermont Grégory
Publication year - 2011
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20332
Subject(s) - mathematics , binary tree , limit (mathematics) , random binary tree , probabilistic logic , scaling limit , scaling , combinatorics , binary number , tree (set theory) , binary search tree , discrete mathematics , topology (electrical circuits) , statistical physics , mathematical analysis , geometry , physics , statistics , arithmetic
We prove that a uniform, rooted unordered binary tree (also known as rooted, binary Pólya tree) with n leaves 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. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 467–501, 2011