14h00: Cecilia Holmgren, Uppsala University.

Random Records and Cuttings in Split Trees.

I will discuss the number of random records in an arbitrary split tree with n vertices (or equivalently, the number of random cuttings required to eliminate the tree). I will explain how a classical limit theorem for convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. After normalization the distributions are shown to be asymptotically weakly 1-stable. This work is a generalization of my earlier results for the random binary search tree, which is one specific case of split trees. Other important examples of split trees include m-ary search trees, quadtrees, medians of (2k+1)-trees, simplex trees, tries and digital search trees.