STOR Colloquium: Louigi Addario-Berry, McGill University

Louigi Addario-Berry
McGill University

Assumptionless bounds for Galton-Watson trees and

random combinatorial 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 \geq 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 (A-B, Devroye and Janson, 2013). 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 the Lévy’s concentration function for random walks may be used to show that the random variable ht(T)/wid(T) always 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.

Refreshments will be served at 3:00pm in the 3^rd floor lounge of Hanes Hall