Skip to Main content Skip to Navigation
Conference papers

Simply generated trees, conditioned Galton―Watson trees, random allocations and condensation: Extended abstract

Abstract : We give a unified treatment of the limit, as the size tends to infinity, of random simply generated trees, including both the well-known result in the standard case of critical Galton-Watson trees and similar but less well-known results in the other cases (i.e., when no equivalent critical Galton-Watson tree exists). There is a well-defined limit in the form of an infinite random tree in all cases; for critical Galton-Watson trees this tree is locally finite but for the other cases the random limit has exactly one node of infinite degree. The random infinite limit tree can in all cases be constructed by a modified Galton-Watson process. In the standard case of a critical Galton-Watson tree, the limit tree has an infinite "spine", where the offspring distribution is size-biased. In the other cases, the spine has finite length and ends with a vertex with infinite degree. A node of infinite degree in the limit corresponds to the existence of one node with very high degree in the finite random trees; in physics terminology, this is a type of condensation. In simple cases, there is one node with a degree that is roughly a constant times the number of nodes, while all other degrees are much smaller; however, more complicated behaviour is also possible. The proofs use a well-known connection to a random allocation model that we call balls-in-boxes, and we prove corresponding results for this model.
Complete list of metadata

Cited literature [29 references]  Display  Hide  Download
Contributor : Coordination Episciences Iam Connect in order to contact the contributor
Submitted on : Friday, September 11, 2015 - 12:54:48 PM
Last modification on : Tuesday, March 7, 2017 - 3:19:15 PM
Long-term archiving on: : Tuesday, December 29, 2015 - 12:33:31 AM


Publisher files allowed on an open archive


Distributed under a Creative Commons Attribution 4.0 International License




Svante Janson. Simply generated trees, conditioned Galton―Watson trees, random allocations and condensation: Extended abstract. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12) , 2012, Montreal, Canada. pp.479-490, ⟨10.46298/dmtcs.3013⟩. ⟨hal-01197228⟩



Record views


Files downloads