Invited Presentations
Luc Devroye, McGill University, Canada
Weighted Heights of Random Trees
The height of a tree is the maximal path distance between a leaf and the root. It is convenient to attach weights to edges and consider the weighted height in order to obtain a more universal model of tree. We introduce a random weighted model that captures most random search trees and random recursive trees that we know of. For most nodes in such trees, subtree sizes and weights of edges emanating from it are allowed to be dependent in a rather general way. Using the multivariate theory of large deviations, we obtain the first asymptotic term of the height. In the talk, we will survey many applications of our result.
This is joint work with Nicolas Broutin and Erin McLeish.
