Simply Generated Unrooted Plane Trees

Ramzews, Leon; Stufler, Benedikt (2019): Simply Generated Unrooted Plane Trees. In: Alea-Latin American Journal of Probability and Mathematical Statistics, Vol. 16, No. 1: pp. 333-359

Abstract

We study random unrooted plane trees with n vertices sampled according to the weights corresponding to the vertex-degrees. Our main result shows that if the generating series of the weights has positive radius of convergence, then this model of random trees may be approximated geometrically by a Galton-Watson tree conditioned on having a large random size. This implies that a variety of results for the well-studied planted case also hold for unrooted trees, including Gromov-Hausdorff-Prokhorov scaling limits, tail-bounds for the diameter, distributional graph limits, and limits for the maximum degree. Our work complements results by Wang (2016), who studied random unrooted plane trees whose diameter tends to infinity.

• Item Type: Journal article
• Faculties: Mathematics, Computer Science and Statistics > Mathematics
• Subjects: 500 Science > 510 Mathematics
• ISSN: 1980-0436
• Language: English