Voronoi cells in random split trees
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. The 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. The 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.
- Novel characteristics of split trees by use of renewal theory
- The asymptotic distribution of cluster sizes for supercritical percolation on random split trees
- Split trees -- a unifying model for many important random trees of logarithmic height: a brief survey
- scientific article; zbMATH DE number 6683495
- scientific article; zbMATH DE number 7703259
- Competing first passage percolation on random regular graphs
- Fixed speed competition on the configuration model with infinite variance degrees: unequal speeds
- Fringe trees, Crump-Mode-Jagers branching processes and \(m\)-ary search trees
- scientific article; zbMATH DE number 3090543 (Why is no real title available?)
- Measure-valued Pólya urn processes
- Novel characteristics of split trees by use of renewal theory
- On a conjecture by Chapuy about Voronoï cells in large maps
- On tessellations of random maps and the \(t_g\)-recurrence
- On the profile of random trees
- Probability: A Graduate Course
- Random recursive trees and preferential attachment trees are random split trees
- The asymptotic distribution of cluster sizes for supercritical percolation on random split trees
- The fluctuations of the giant cluster for percolation on random split trees
- The profile of binary search trees
- The total path length of split trees
- The winner takes it all
- Universal Limit Laws for Depths in Random Trees
- Voronoi tessellations in the CRT and continuum random maps of finite excess
- Width of a scale-free tree
This page was built for publication: Voronoi cells in random split trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6584605)
