Assumptionless Bounds for Random Trees (Keynote Speakers)

Abstract

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.