Width and height of conditioned Galton-Watson trees

Speaker  Svante Janson

Affiliation  Uppsala University

Host  Yuval Peres

Duration  00:51:56

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.
> Width and height of conditioned Galton-Watson trees