Voronoi cells in random split trees
Annales Henri Lebesgue, Volume 7 (2024), pp. 123-159.


Keywords Random split trees, Voronoi cells in graphs, competition processes, profile, fringe 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 nexp(-constlogn). 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).


[AACFG18] Addario-Berry, Louigi; Angel, Omer; Chapuy, Guillaume; Fusy, Éric; Goldschmidt, Christina Voronoi tessellations in the CRT and continuum random maps of finite excess, 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), 2018, pp. 933-946 | Zbl

[ADMP17] Antunović, Tonći; Dekel, Yael; Mossel, Elchanan; Peres, Yuval Competing first passage percolation on random regular graphs, Random Struct. Algorithms, Volume 50 (2017) no. 4, pp. 534-583 | DOI | MR | Zbl

[BCH19] Berzunza, Gabriel; Cai, Xing Shi; Holmgren, Cecilia The fluctuations of the giant cluster for percolation on random split trees (2019) | arXiv

[BH12] Broutin, Nicolas; Holmgren, Cecilia The total path length of split trees, Ann. Appl. Probab., Volume 22 (2012) no. 5, pp. 1745-1777 | MR | Zbl

[BH21] Berzunza, Gabriel; Holmgren, Cecilia The asymptotic distribution of cluster sizes for supercritical percolation on random split trees (2021) | arXiv

[BHK15] Baroni, Enrico; van der Hofstad, Remco; Komjáthy, Júlia Fixed speed competition on the configuration model with infinite variance degrees: unequal speeds, Electron. J. Probab., Volume 20 (2015), 116 | MR | Zbl

[CDJH01] Chauvin, Brigitte; Drmota, Michael; Jabbour-Hattab, Jean The profile of binary search trees, Ann. Appl. Probab., Volume 11 (2001) no. 4, pp. 1042-1062 | MR | Zbl

[Cha19] Chapuy, Guillaume On tessellations of random maps and the t g -recurrence, Probab. Theory Relat. Fields, Volume 174 (2019) no. 1-2, pp. 477-500 | DOI | MR | Zbl

[Dev98] Devroye, Luc Universal limit laws for depths in random trees, SIAM J. Comput., Volume 28 (1998) no. 2, pp. 409-432 | DOI | MR | Zbl

[DG97] Drmota, Michael; Gittenberger, Bernhard On the profile of random trees, Random Struct. Algorithms, Volume 10 (1997) no. 4, pp. 421-451 | DOI | MR | Zbl

[DH16] Deijfen, Maria; Hofstad, Remco van der The winner takes it all, Ann. Appl. Probab., Volume 26 (2016) no. 4, pp. 2419-2453 | MR | Zbl

[GK54] Gnedenko, Boris V.; Kolmogorov, Andrei N. Limit Distributions for Sums of Independent Random Variables, Addison-Wesley Publishing Group, 1954 | Zbl

[Gui17] Guitter, Emmanuel On a conjecture by Chapuy about Voronoi cells in large maps, J. Stat. Mech. Theory Exp., Volume 2017 (2017) no. 10, 103401 | DOI | MR | Zbl

[Gut05] Gut, Allan Probabiliy: a Graduate Course, Springer Texts in Statistics, Springer, 2005 | Zbl

[HJ17] Holmgren, Cecilia; Janson, Svante Fringe trees, Crump–Mode–Jagers branching processes and m-ary search trees, Probab. Surv., Volume 14 (2017), pp. 53-154 | MR | Zbl

[HK15] van der Hofstad, Remco; Komjáthy, Júlia Fixed speed competition on the configuration model with infinite variance degrees: equal speeds (2015) | arXiv

[Hol12] Holmgren, Cecilia Novel characteristics of split trees by use of renewal theory, Electron. J. Probab., Volume 17 (2012), 5 | MR | Zbl

[Jan19] Janson, Svante Random recursive trees and preferential attachment trees are random split trees, Comb. Probab. Comput., Volume 28 (2019) no. 1, pp. 81-99 | DOI | MR | Zbl

[Kat05] Katona, Zsolt Width of a scale-free tree, J. Appl. Probab., Volume 42 (2005) no. 3, pp. 839-850 | DOI | MR | Zbl

[MM17] Mailler, Cécile; Marckert, Jean-François Measure-valued Pólya processes, Electron. J. Probab., Volume 22 (2017), 26, p. 33 | Zbl