2026-07-22T20:48:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:8927 2024-03-06T10:43:46Z ddc:004 open_access

Local Limits of Large Galton-Watson Trees Rerooted at a Random Vertex Stufler, Benedikt Galton-Watson trees local weak limits We prove limit theorems describing the asymptotic behaviour of a typical vertex in random simply generated trees as their sizes tends to infinity. In 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). Our main contribution lies in the condensation regime where vertices of macroscopic degree appear. Here 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 behaviours 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 important case where the offspring distribution follows a power law up to a factor that varies slowly at infinity. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Benedikt Stufler 2018 Is Part Of LIPIcs, Volume 110, 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.AofA.2018.34 urn:nbn:de:0030-drops-89276 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.34 eng https://creativecommons.org/licenses/by/3.0/legalcode