Speaker Svante Janson
Host Yuval Peres
Affiliation Uppsala University
Date recorded 7 May 2010
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.)
©2010 Microsoft Corporation. All rights reserved.