Climbing and Destroying Random Trees

Abstract

In this talk, I will present results and the methods of proof for two shape parameters in some random tree families. The first tree statistic considered is the number of steps, that are necessary to "climb" a random tree of size n. Such a statistic can be equivalently formulated as the size of the incomplete (or one-sided) versions of the trees in question, which has recently been studied e.g. by Itoh and Mahmoud for the model of binary interval trees. I will give limit theorems for such a tree statistic under different tree models. The other tree statistic deals with the number of random "cuts" that are necessary to destroy a tree of size n. Limiting distribution for certain classes of trees are presented.