Split trees -- A unifying model for many important random trees of logarithmic height

Algebraic and Enumerative Combinatorics

31 January 10:30 - 11:20

Cecilia Holmgren - Uppsala University

Split trees were introduced by Devroye (1998) as a novel approach for unifying many important random trees of logarithmic height. They are interesting not least because of their usefulness as models of sorting algorithms in computer science; for instance the well-known Quicksort algorithm (introduced by Hoare [1960]) can be depicted as a binary search tree (which is one example of a split tree). In 2012 I introduced renewal theory as a novel approach for studying split trees*. This approach has proved to be highly useful for investigating such trees and has allowed me to show several general results valid for all split trees. In my presentation, I will introduce split trees and illustrate some of my results for this large class of random trees, e.g. on the size, total path length, number of cuttings and number of inversions as well as on the size of the giant component after bond percolation. * Holmgren C., Novel characteristic of split trees by use of renewal theory. Electronic Journal of Probability 2012.
Sara Billey
University of Washington
Petter Brändén
KTH Royal Institute of Technology
Sylvie Corteel
Université Paris Diderot, Paris 7
Svante Linusson
KTH Royal Institute of Technology


Svante Linusson


For practical matters at the Institute, send an e-mail to