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
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom