Premium
The CRT is the scaling limit of random dissections
Author(s) -
Curien Nicolas,
Haas Bénédicte,
Kortchemski Igor
Publication year - 2015
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.20554
Subject(s) - geodesic , mathematics , scaling limit , scaling , limit (mathematics) , boltzmann constant , random graph , hausdorff space , combinatorics , markov chain , brownian motion , tree (set theory) , statistical physics , graph , discrete mathematics , geometry , physics , mathematical analysis , statistics , quantum mechanics
–We study the graph structure of large random dissections of polygons sampled according to Boltzmann weights, which encompasses the case of uniform dissections or uniform p ‐angulations. As their number of vertices n goes to infinity, we show that these random graphs, rescaled byn − 1 / 2, converge in the Gromov–Hausdorff sense towards a multiple of Aldous' Brownian tree when the weights decrease sufficiently fast. The scaling constant depends on the Boltzmann weights in a rather amusing and intriguing way, and is computed by making use of a Markov chain which compares the length of geodesics in dissections with the length of geodesics in their dual trees. © 2014 Wiley Periodicals, Inc. Random Struct. Alg., 47, 304–327, 2015