Discrete Mathematics & Theoretical Computer Science (Dec 2004)

The Width of Galton- Watson Trees Conditioned by the Size

  • Michael Drmota,
  • Bernhard Gittenberger

Journal volume & issue
Vol. 6, no. 2

Abstract

Read online

It is proved that the moments of the width of Galton-Watson trees of size n and with offspring variance σ 2 are asymptotically given by (σ√ n) p m p where m p are the moments of the maximum of the local time of a standard scaled Brownian excursion. This is done by combining a weak limit theorem and a tightness estimate. The method is quite general and we state some further applications.