Voronoi cells in random split trees

We study the sizes of the Voronoi cells of k uniformly chosen vertices in a random split tree of size n. We prove that, for n large, the largest of these k Voronoi cells contains most of the vertices, while the sizes of the remaining ones are essentially all of order n exp(−const^√log n). This “winner-takes-all” phenomenon persists if we modify the definition of the Voronoi cells by (a) introducing random edge lengths (with suitable moment assumptions), and (b) assigning different “influence” parameters (called “speeds” in the paper) to each of the k vertices. Our findings are in contrast to corresponding results on random uniform trees and on the continuum random tree, where it is known that the vector of the relative sizes of the k Voronoi cells is asymptotically uniformly distributed on the (k − 1)-dimensional simplex. Two intermediary steps in the proof of our main result may be of independent interest because of the information they give on the typical shape of large random split trees: we prove convergence in probability of their “profile”, and we prove asymptotic results for the size of fringe trees (trees rooted at an ancestor of a uniform random node).