Skip to main content
eScholarship
Open Access Publications from the University of California

Scaling limits of random trees

  • Author(s): Rizzolo, Douglas Paul
  • Advisor(s): Pitman, James W
  • et al.
Abstract

We investigate scaling limits of several types of random trees. The study of scaling limits of random trees was initiated by Aldous in the early 1990's. One of the primary goals of his work was to study the uniform distribution on trees with n vertices as n grew to infinity, as well as uniform distributions on other combinatorially motivated models of trees with n vertices. We are motivated by studying combinatorial models of random trees with n leaves as n goes to infinity. Conditioning on the number of leaves rather than the number of vertices has significant consequences in terms of what techniques are applicable. We deal with these issues by developing a general theory for scaling limits of Markov branching trees whose size is given by their number of vertices with out-degree in a fixed set. This general theory is then applied to obtain scaling limits of Galton-Watson trees conditioned on their number of vertices with out-degree in a fixed set. We also show that many combinatorial models of trees with n leaves can be realized as Galton-Watson trees (or probabilistic transforms thereof) conditioned to have n leaves.

Main Content
Current View