Voronoi cells in random split trees (Q6584605)

This paper studies the sizes of the Voronoi cells of split trees. Given a graph \(G\) on \(n\) vertices, and a set of \(k\) vertices \(U_{1},U_{2},\ldots, U_{k}\) of \(G\) chosen uniformly at random, the Voronoi cell \(\text{Vor}(U_{i})\) of \(U_{i}\) consists of those vertices which are closer in graph distance to \(U_{i}\) than to any other \(U_{j}\) (ties being resolved by some arbitrary rule). The object of study is then the vector \((\vert \text{Vor}(U_{1})\vert /n, \vert \text{Vor}(U_{2})\vert /n,\ldots, \vert \text{Vor}(U_{k})\vert/n)\) and in particular its limiting behaviour as \(n\rightarrow\infty\), which we shall refer to as the limiting vector. For example, when \(G\) is a uniform random tree on \(n\) vertices, recent results from [\textit{L. Addario-Berry} et al., in: Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms, SODA 2018, New Orleans, LA, USA, January 7--10, 2018. Philadelphia, PA: Society for Industrial and Applied Mathematics (SIAM); New York, NY: Association for Computing Machinery (ACM). 933--946 (2018; Zbl 1403.68143)] shows that the limiting vector has uniform distribution on the \((k-1)\)-dimensional simplex: indeed they also show this holds more generally for any graph model which converges to the Brownian continuum random tree (CRT) in the Gromov-Hausdorff-Prokhorov topology.\N\NThe paper under review considers random \(n\)-vertex split trees, a rather broad class of models of random trees including binary search trees, random recursive trees and preferential attachment trees. The first main result is that the largest Voronoi cell in an \(n\)-node random split tree contains proportion \(1-o(1)\) of the vertices -- the `winner-takes-all effect'. Further, they give upper bounds of the form \(ne^{-c\sqrt{n}}\) on the size of the other Voronoi cells. Indeed, these results also hold when we replace graph distance by random i.i.d. edge lengths (of finite variance, or heavy-tailed with finite means) and define the Voronoi cells with respect to that distance. That the behaviour is different from the uniform trees is not wholly surprising -- for example, uniform random trees typically have a height of about \(\sqrt{n}\) whereas for random split trees, the height is about \(\log(n)\). The authors note it is reasonable to speculate that similar limiting behaviour might happen for random graph models similar to random split trees such as preferential attachment graphs, but also that their proofs do not seem to extend straightforwardly to cover this case.\N\NThe authors also note that their ideas give insight into the typical shape of a random split tree, and discuss a link with models of competing epidemics. Key proof techniques include a central limit theorem for the heights of \(k\) random nodes and a result about convergence of extended fringe trees.