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 metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal-ens-lyon.archives-ouvertes.fr/ensl-01408155
Contributor : Benedikt Stufler <>
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

File

pointed.pdf
Files produced by the author(s)

Identifiers

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

Collections

Citation

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

Share

Metrics

Record views

90

Files downloads

178