Till innehåll på sidan

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

Tid: Fr 2020-01-31 kl 10.30 - 11.20

Plats: Institut Mittag-Leffler, Seminar Hall Kuskvillan

Medverkande: Cecilia Holmgren, Uppsala Universiy

Exportera till kalender

Abstract

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.