Random trees are short (but not too short)

ESB 2012

I will discuss some new upper and lower bounds on the height of random trees. The first result is that, under very general assumptions, trees with a given degree sequence, simply generated trees and Bienaymé-Galton-Watson trees of size $n$ have height \( O(\sqrt{n}) \) with Gaussian tails (and height \( O(\sqrt{n}) \) in the high variance regime). Moreover, we show that all critical Bienaymé-Galton-Watson trees of size $n$ have height \( \omega(\log(n)) \).  The proofs are mostly combinatorial and are based on the Foata-Fuchs bijection between trees and sequences. If time permits, I will also discuss some precise asymptotics for the height of critical Bienaymé-Galton-Watson with degree distribution in the domain of attraction of a Cauchy distribution. The results resolve various conjectures from the literature and are based on a work with Louigi Addario-Berry and a work in progress with Louigi Addario-Berry and Igor Kortchemski.