×

The cut-tree of large recursive trees. (English. French summary) Zbl 1351.60010

The cut-tree records the key steps of the destruction process, where a graph is progressively destroyed by cutting its edges one after the other in a uniform order. It can be viewed as a random metric space equipped with a natural probability mass. In this paper, the author shows that the cut-tree of a random recursive tree of size \(n\), rescaled by the factor \(n^{-1}\ln n\), converges in probability to the unit interval endowed with the usual distance and Lebesgue measure as \(n \rightarrow \infty\), in the sense of Gromov-Hausdorff-Prokhorov. Some results of M. F. Kuba and A. Panholzer [Online J. Anal. Comb. 9, Article 7, 26 p. (2014; Zbl 1300.05285)] on multiple isolation of nodes in large random recursive trees are extended in this paper.

MSC:

60C05 Combinatorial probability
05D40 Probabilistic methods in extremal combinatorics, including polynomial methods (combinatorial Nullstellensatz, etc.)
60D05 Geometric probability and stochastic geometry
60F15 Strong limit theorems
05C05 Trees

Citations:

Zbl 1300.05285

References:

[1] L. Addario-Berry, N. Broutin and C. Holmgren. Cutting down trees with a Markov chainsaw. Ann. Appl. Probab. 24 (2014) 2297-2339. · Zbl 1352.60009 · doi:10.1214/13-AAP978
[2] J. Bertoin. Fires on trees. Ann. Inst. Henri Poincaré Probab. Stat. 48 (2012) 909-921. · Zbl 1263.60083 · doi:10.1214/11-AIHP435
[3] J. Bertoin. Sizes of the largest clusters for supercritical percolation on random recursive trees. Random Structures Algorithms 44 (2014) 29-44. · Zbl 1280.05117 · doi:10.1002/rsa.20448
[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. · Zbl 1279.60035 · doi:10.1214/12-AAP877
[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. · Zbl 1187.05068 · doi:10.1002/rsa.20233
[6] K. B. Erickson. Strong renewal theorems with infinite mean. Trans. Amer. Math. Soc. 151 (1970) 263-291. · Zbl 0212.51601 · doi:10.2307/1995628
[7] A. Greven, P. Pfaffelhuber and A. Winter. Convergence in distribution of random metric measure spaces (\(\varLambda\)-coalescent measure trees). Probab. Theory Related Fields 145 (2009) 285-322. · Zbl 1215.05161 · doi:10.1007/s00440-008-0169-3
[8] M. Gromov. Metric Structures for Riemannian and Non-Riemannian Spaces. Progress in Mathematics 152 . Birkhäuser, Boston, MA, 1999. · Zbl 0953.53002
[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. · Zbl 1259.60033 · doi:10.1214/11-AOP686
[10] C. Holmgren. Random records and cuttings in binary search trees. Combin. Probab. Comput. 19 (2010) 391-424. · Zbl 1215.05162 · doi:10.1017/S096354830999068X
[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. · Zbl 1213.05037 · doi:10.1239/aap/1300198517
[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. · Zbl 1133.60012 · doi:10.1214/ECP.v12-1253
[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. · Zbl 1063.60018 · doi:10.1007/978-3-0348-7915-6_24
[14] S. Janson. Random cutting and records in deterministic and random trees. Random Structures Algorithms 29 (2006) 139-179. · Zbl 1120.05083 · doi:10.1002/rsa.20086
[15] O. Kallenberg. Foundations of Modern Probability , 2nd edition. Probability and its Applications (New York) . Springer, New York, 2002. · Zbl 0996.60001
[16] M. Kuba and A. Panholzer. Multiple isolation of nodes in recursive trees. Preprint, 2013. Available at . · Zbl 1300.05285
[17] R. Lyons, R. Pemantle and Y. Peres. Conceptual proofs of \(L\log L\) citeria for mean behaviour of branching processes. Ann. Probab. 23 (1995) 1125-1138. · Zbl 0840.60077 · doi:10.1214/aop/1176988176
[18] A. Meir and J. W. Moon. Cutting down random trees. J. Aust. Math. Soc. 11 (1970) 313-324. · Zbl 0196.27602 · doi:10.1017/S1446788700006698
[19] A. Meir and J. W. Moon. Cutting down recursive trees. Math. Biosci. 21 (1974) 173-181. · Zbl 0288.05102 · doi:10.1016/0025-5564(74)90013-3
[20] A. Panholzer. Destruction of recursive trees. In Mathematics and Computer Science III. Trends Math. 267-280. Birkhäuser, Basel, 2004. · Zbl 1060.05022 · doi:10.1007/978-3-0348-7915-6_29
[21] A. Panholzer. Cutting down very simple trees. Quaest. Math. 29 (2006) 211-227. · Zbl 1120.05020 · doi:10.2989/16073600609486160
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.