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.
Type de document :
Communication dans un congrès
Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12) , 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.479-490, 2012, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [29 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01197228
Contributeur : Coordination Episciences Iam <>
Soumis le : vendredi 11 septembre 2015 - 12:54:48
Dernière modification le : mardi 7 mars 2017 - 15:19:15
Document(s) archivé(s) le : mardi 29 décembre 2015 - 00:33:31

Fichier

dmAQ0135.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Licence


Distributed under a Creative Commons Paternité 4.0 International License

Identifiants

  • HAL Id : hal-01197228, version 1

Collections

Citation

Svante Janson. Simply generated trees, conditioned Galton―Watson trees, random allocations and condensation: Extended abstract. Broutin, Nicolas and Devroye, Luc. 23rd International Meeting on Probabilistic, Combinatorial, and Asymptotic Methods in the Analysis of Algorithms (AofA'12) , 2012, Montreal, Canada. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AQ, 23rd Intern. Meeting on Probabilistic, Combinatorial, and Asymptotic Methods for the Analysis of Algorithms (AofA'12), pp.479-490, 2012, DMTCS Proceedings. 〈hal-01197228〉

Partager

Métriques

Consultations de la notice

194

Téléchargements de fichiers

154