Width and height of conditioned Galton-Watson trees


May 7, 2010


Svante Janson


Uppsala University


Consider a random Galton-Watson tree conditioned to have size n.
We assume that the offspring distribution has mean 1 and finite variance, but no further moment conditions.
It is well-known that the width and height both are of the order n1/2 (see for example Aldous (1991) for much more detailed results on the shape). I will talk about about proving tail estimates, for example P(width > k) < exp(-c k2/n). (Note that no such exponential tail bounds are assumed for the offspring distribution.) The proof uses a finite version of the size-biazed Galton-Watson tree studied by Lyons, Pemantle and Peres (1995).
(Joint work with Louigi Addario-Berry and Luc Devroye.)


Svante Janson

Svante Janson received his Ph.D. at the Uppsala University in 1977 & 1984, and has been a Professor of Mathematics at the Uppsala University since 1987. He has written 4 books and over a hundred papers. He is also a member of the Royal Swedish Academy of Sciences from 1994.