Premium
The continuum random tree is the scaling limit of unlabeled unrooted trees
Author(s) -
Stufler Benedikt
Publication year - 2019
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.20833
Subject(s) - mathematics , random tree , combinatorics , conjecture , scaling limit , random graph , tree (set theory) , scaling , hausdorff space , limit (mathematics) , vertex (graph theory) , brownian motion , graph , discrete mathematics , mathematical analysis , statistics , geometry , motion planning , artificial intelligence , computer science , robot
We show that the uniform unlabeled unrooted tree with n vertices and vertex degrees in a fixed set converges in the Gromov‐Hausdorff sense after a suitable rescaling to the Brownian continuum random tree. This confirms a conjecture by Aldous (1991). We also establish Benjamini‐Schramm convergence of this model of random trees and provide a general approximation result, that allows for a transfer of a wide range of asymptotic properties of extremal and additive graph parameters from Pólya trees to unrooted trees.