The continuum random tree is the scaling limit of unlabeled unrooted trees. Issue 2 (11th December 2018)

• Record Type: Journal Article
• Authors: Stufler, Benedikt
• Is Part Of: Random structures & algorithms. Volume 55:Issue 2(2019)
• Page Start: 496
• Page End: 528
• Publication Date: 2018-12-11
• Subjects: continuum random tree -- graph limits -- random unlabelled trees; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20833
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : 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.