2026-08-10T20:24:52Z https://drops.dagstuhl.de/oai

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

Assumptionless Bounds for Random Trees (Keynote Speakers) Addario-Berry, Louigi Random trees simply generated trees Let T be any Galton-Watson tree. Write vol(T) for the volume of T (the number of nodes), ht(T) for the height of T (the greatest distance of any node from the root) and wid(T) for the width of T (the greatest number of nodes at any level). We study the relation between vol(T), ht(T) and wid(T). In the case when the offspring distribution p = (p_i, i >= 0) has mean one and finite variance, both ht(T) and wid(T) are typically of order vol(T)^{1/2}, and have sub-Gaussian upper tails on this scale. Heuristically, as the tail of the offspring distribution becomes heavier, the tree T becomes "shorter and bushier". I will describe a collection of work which can be viewed as justifying this heuristic in various ways In particular, I will explain how classical bounds on Lévy's concentration function for random walks may be used to show that for any offspring distribution, the random variable ht(T)/wid(T) has sub-exponential tails. I will also describe a more combinatorial approach to coupling random trees with different degree sequences which allows the heights of randomly sampled vertices to be compared. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Louigi Addario-Berry 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.2 urn:nbn:de:0030-drops-88951 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.AofA.2018.2 eng https://creativecommons.org/licenses/by/3.0/legalcode