HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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.
Document type :
Preprints, Working Papers, ...
Complete list of metadata

Cited literature [15 references]  Display  Hide  Download

Contributor : Benedikt Stufler Connect in order to contact the contributor
Submitted on : Wednesday, February 14, 2018 - 9:38:43 PM
Last modification on : Tuesday, November 19, 2019 - 11:52:52 AM
Long-term archiving on: : Sunday, May 6, 2018 - 11:40:24 AM


Files produced by the author(s)


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



Benedikt Stufler. Local limits of large Galton–Watson trees rerooted at a random vertex. 2018. ⟨ensl-01408155v2⟩



Record views


Files downloads