Markus Heydenreich

Voronoi cells in random split trees

Consider a large graph G, and choose k vertices uniformly. We study the proportional size of the Voronoi cells of these k vertices as the number of vertices increases (but k kept fix). We identify the scaling of proportional sizes of the Voronoi cells for the case that G is a random split tree. Indeed, in this case, the largest of these k Voronoi cells contains most of the vertices, while the sizes of the remaining ones are of smaller order. This “winner-takes-all” phenomenon persists if we modify the definition of the Voronoi cells by introducing random edge lengths (with suitable moment assumptions), or assigning different influence parameters (“speeds”) to each of the k vertices. We achieve this by investigating the typical shape of large random split trees.
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.
Based on joint work with Cécile Mailler and Alexander Drewitz.