The cut-tree of large recursive trees
Annales de l'I.H.P. Probabilités et statistiques, Volume 51 (2015) no. 2, pp. 478-488.

Imagine a graph which is progressively destroyed by cutting its edges one after the other in a uniform random order. The so-called cut-tree records key steps of this destruction process. It can be viewed as a random metric space equipped with a natural probability mass. In this work, we show that the cut-tree of a random recursive tree of size n, rescaled by the factor n -1 lnn, converges in probability as n in the sense of Gromov–Hausdorff–Prokhorov, to the unit interval endowed with the usual distance and Lebesgue measure. This enables us to explain and extend some recent results of Kuba and Panholzer (Multiple isolation of nodes in recursive trees (2013) Preprint) on multiple isolation of nodes in large random recursive trees.

Imaginons la destruction progressive d’un graphe auquel on retire ses arêtes une à une dans un ordre aléatoire uniforme. Le “cut-tree” permet de coder les étapes essentielles du processus de destruction; il peut être vu comme un espace métrique aléatoire muni d’une mesure de probabilité naturelle. Dans cet article, nous montrons que le cut-tree d’un arbre récursif aléatoire de taille n, et renormalisé par un facteur n -1 lnn, converge en probabilité quand n au sens de Gromov–Hausdorff–Prokhorov, vers l’intervale unité muni de la distance usuelle et de la mesure de Lebesgue. Ceci nous permet d’expliquer et d’étendre des résultats récents de Kuba and Panholzer (Multiple isolation of nodes in recursive trees (2013) Preprint) sur l’isolation multiple de sommets dans un grand arbre récursif aléatoire.

DOI: 10.1214/13-AIHP597
Classification: 60D05, 60F15
Keywords: random recursive tree, destruction of graphs, Gromov–Hausdorff–Prokhorov convergence, multiple isolation of nodes
@article{AIHPB_2015__51_2_478_0,
     author = {Bertoin, Jean},
     title = {The cut-tree of large recursive trees},
     journal = {Annales de l'I.H.P. Probabilit\'es et statistiques},
     pages = {478--488},
     publisher = {Gauthier-Villars},
     volume = {51},
     number = {2},
     year = {2015},
     doi = {10.1214/13-AIHP597},
     mrnumber = {3335011},
     zbl = {1351.60010},
     language = {en},
     url = {http://www.numdam.org/articles/10.1214/13-AIHP597/}
}
TY  - JOUR
AU  - Bertoin, Jean
TI  - The cut-tree of large recursive trees
JO  - Annales de l'I.H.P. Probabilités et statistiques
PY  - 2015
SP  - 478
EP  - 488
VL  - 51
IS  - 2
PB  - Gauthier-Villars
UR  - http://www.numdam.org/articles/10.1214/13-AIHP597/
DO  - 10.1214/13-AIHP597
LA  - en
ID  - AIHPB_2015__51_2_478_0
ER  - 
%0 Journal Article
%A Bertoin, Jean
%T The cut-tree of large recursive trees
%J Annales de l'I.H.P. Probabilités et statistiques
%D 2015
%P 478-488
%V 51
%N 2
%I Gauthier-Villars
%U http://www.numdam.org/articles/10.1214/13-AIHP597/
%R 10.1214/13-AIHP597
%G en
%F AIHPB_2015__51_2_478_0
Bertoin, Jean. The cut-tree of large recursive trees. Annales de l'I.H.P. Probabilités et statistiques, Volume 51 (2015) no. 2, pp. 478-488. doi : 10.1214/13-AIHP597. http://www.numdam.org/articles/10.1214/13-AIHP597/

[1] L. Addario-Berry, N. Broutin and C. Holmgren. Cutting down trees with a Markov chainsaw. Ann. Appl. Probab. 24 (2014) 2297–2339. | DOI | MR | Zbl

[2] J. Bertoin. Fires on trees. Ann. Inst. Henri Poincaré Probab. Stat. 48 (2012) 909–921. | DOI | Numdam | MR | Zbl

[3] J. Bertoin. Sizes of the largest clusters for supercritical percolation on random recursive trees. Random Structures Algorithms 44 (2014) 29–44. | DOI | MR | Zbl

[4] J. Bertoin and G. Miermont. The cut-tree of large Galton–Watson trees and the Brownian CRT. Ann. Appl. Probab. 23 (2013) 1469–1493. | DOI | MR | Zbl

[5] M. Drmota, A. Iksanov, M. Möhle and U. Rösler. A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree. Random Structures Algorithms 34 (2009) 319–336. | DOI | MR | Zbl

[6] K. B. Erickson. Strong renewal theorems with infinite mean. Trans. Amer. Math. Soc. 151 (1970) 263–291. | DOI | MR | Zbl

[7] A. Greven, P. Pfaffelhuber and A. Winter. Convergence in distribution of random metric measure spacesProbab. Theory Related Fields 145 (2009) 285–322. | DOI | MR | Zbl

[8] M. Gromov. Metric Structures for Riemannian and Non-Riemannian Spaces. Progress in Mathematics 152. Birkhäuser, Boston, MA, 1999. | MR | Zbl

[9] B. Haas and G. Miermont. Scaling limits of Markov branching trees, with applications to Galton–Watson and random unordered trees. Ann. Probab. 40 (2012) 2589–2666. | DOI | MR | Zbl

[10] C. Holmgren. Random records and cuttings in binary search trees. Combin. Probab. Comput. 19 (2010) 391–424. | DOI | MR | Zbl

[11] C. Holmgren. A weakly 1-stable distribution for the number of random records and cuttings in split trees. Adv. in Appl. Probab. 43 (2011) 151–177. | DOI | MR | Zbl

[12] A. Iksanov and M. Möhle. A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree. Electron. Commun. Probab. 12 (2007) 28–35. | DOI | MR | Zbl

[13] S. Janson. Random records and cuttings in complete binary trees. In Mathematics and Computer Science III. Trends Math. 241–253. Birkhäuser, Basel, 2004. | MR | Zbl

[14] S. Janson. Random cutting and records in deterministic and random trees. Random Structures Algorithms 29 (2006) 139–179. | DOI | MR | Zbl

[15] O. Kallenberg. Foundations of Modern Probability, 2nd edition. Probability and its Applications (New York). Springer, New York, 2002. | DOI | MR | Zbl

[16] M. Kuba and A. Panholzer. Multiple isolation of nodes in recursive trees. Preprint, 2013. Available at http://arxiv.org/abs/1305.2880. | MR | Zbl

[17] R. Lyons, R. Pemantle and Y. Peres. Conceptual proofs of LlogL citeria for mean behaviour of branching processes. Ann. Probab. 23 (1995) 1125–1138. | DOI | MR | Zbl

[18] A. Meir and J. W. Moon. Cutting down random trees. J. Aust. Math. Soc. 11 (1970) 313–324. | DOI | MR | Zbl

[19] A. Meir and J. W. Moon. Cutting down recursive trees. Math. Biosci. 21 (1974) 173–181. | DOI | Zbl

[20] A. Panholzer. Destruction of recursive trees. In Mathematics and Computer Science III. Trends Math. 267–280. Birkhäuser, Basel, 2004. | MR | Zbl

[21] A. Panholzer. Cutting down very simple trees. Quaest. Math. 29 (2006) 211–227. | DOI | MR | Zbl

Cited by Sources: