Local limits of large Galton–Watson trees rerooted at a random vertex

Abstract : We discuss various forms of convergence of the vicinity of a uniformly at random selected vertex in random simply generated trees, as the size tends to infinity. For the standard case of a critical Galton–Watson tree conditioned to be large the limit is the invariant random sin-tree constructed by Aldous (1991). In the condensation regime, we describe in complete generality the asymptotic local behaviour from a random vertex up to its first ancestor with large degree. Beyond this distinguished ancestor, different behaviour may occur, depending on the branching weights. In a subregime of complete condensation, we obtain convergence toward a novel limit tree, that describes the asymptotic shape of the vicinity of the full path from a random vertex to the root vertex. This includes the case where the offspring distribution follows a power law up to a factor that varies slowly at infinity.
Type de document :
Pré-publication, Document de travail
Liste complète des métadonnées

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

Contributeur : Benedikt Stufler <>
Soumis le : samedi 3 décembre 2016 - 11:29:30
Dernière modification le : mercredi 7 décembre 2016 - 01:01:42
Document(s) archivé(s) le : mardi 21 mars 2017 - 06:50:44


Fichiers produits par l'(les) auteur(s)


  • HAL Id : ensl-01408155, version 1
  • ARXIV : 1611.01048



Benedikt Stufler. Local limits of large Galton–Watson trees rerooted at a random vertex. 2016. 〈ensl-01408155〉



Consultations de la notice


Téléchargements de fichiers