Inverting the cut-tree transform.

*(English. French summary)*Zbl 1467.60014Summary: We consider fragmentations of an \(\mathbb{R} \)-tree \(T\) driven by cuts arriving according to a Poisson process on \(T\times[0,\infty)\), where the first co-ordinate specifies the location of the cut and the second the time at which it occurs. The genealogy of such a fragmentation is encoded by the so-called cut-tree, which was introduced by J. Bertoin and G. Miermont [Ann. Appl. Probab. 23, No. 4, 1469–1493 (2013; Zbl 1279.60035)] for a fragmentation of the Brownian continuum random tree. The cut-tree was generalised by D. Dieuleveut [Ann. Appl. Probab. 25, No. 4, 2215–2262 (2015; Zbl 1319.60167)] to a fragmentation of the \(\alpha \)-stable trees, \( \alpha\in(1,2)\), and by N. Broutin and M. Wang [Bernoulli 23, No. 4A, 2380–2433 (2017; Zbl 1388.60036)] to the inhomogeneous continuum random trees of D. Aldous and J. Pitman [Probab. Theory Relat. Fields 118, No. 4, 455–482 (2000; Zbl 0969.60015)]. In the first two cases, the projections of the forest-valued fragmentation processes onto the sequence of masses of their constituent subtrees yield an important family of examples of Bertoin’s self-similar fragmentations [J. Bertoin, Ann. Inst. Henri Poincaré, Probab. Stat. 38, No. 3, 319–340 (2002; Zbl 1002.60072)]; in the first case the time-reversal of the fragmentation gives an additive coalescent. Remarkably, in all of these cases, the law of the cut-tree is the same as that of the original \(\mathbb{R} \)-tree.

In this paper, we develop a clean general framework for the study of cut-trees of \(\mathbb{R} \)-trees. We then focus particularly on the problem of reconstruction: how to recover the original \(\mathbb{R} \)-tree from its cut-tree. This has been studied in the setting of the Brownian CRT by N. Broutin and M. Wang [Electron. J. Probab. 22, Paper No. 80, 23 p. (2017; Zbl 1379.60095)], who prove that it is possible to reconstruct the original tree in distribution. We describe an enrichment of the cut-tree transformation, which endows the cut-tree with information we call a consistent collection of routings. We show this procedure is well-defined under minimal conditions on the \(\mathbb{R} \)-trees. We then show that, for the case of the Brownian CRT and the \(\alpha \)-stable trees with \(\alpha\in(1,2)\), the original tree and the Poisson process of cuts thereon can both be almost surely reconstructed from the enriched cut-trees. For the latter results, our methods make essential use of the self-similarity and re-rooting invariance of these trees.

In this paper, we develop a clean general framework for the study of cut-trees of \(\mathbb{R} \)-trees. We then focus particularly on the problem of reconstruction: how to recover the original \(\mathbb{R} \)-tree from its cut-tree. This has been studied in the setting of the Brownian CRT by N. Broutin and M. Wang [Electron. J. Probab. 22, Paper No. 80, 23 p. (2017; Zbl 1379.60095)], who prove that it is possible to reconstruct the original tree in distribution. We describe an enrichment of the cut-tree transformation, which endows the cut-tree with information we call a consistent collection of routings. We show this procedure is well-defined under minimal conditions on the \(\mathbb{R} \)-trees. We then show that, for the case of the Brownian CRT and the \(\alpha \)-stable trees with \(\alpha\in(1,2)\), the original tree and the Poisson process of cuts thereon can both be almost surely reconstructed from the enriched cut-trees. For the latter results, our methods make essential use of the self-similarity and re-rooting invariance of these trees.

##### MSC:

60C05 | Combinatorial probability |

05C05 | Trees |

60G52 | Stable stochastic processes |

60J80 | Branching processes (Galton-Watson, birth-and-death, etc.) |

PDF
BibTeX
XML
Cite

\textit{L. Addario-Berry} et al., Ann. Inst. Henri Poincaré, Probab. Stat. 55, No. 3, 1349--1376 (2019; Zbl 1467.60014)

**OpenURL**

##### References:

[1] | R. Abraham and J.-F. Delmas. The forest associated with the record process on a Lévy tree. Stochastic Process. Appl.123 (9) (2013) 3497-3517. · Zbl 1291.60172 |

[2] | R. Abraham, J.-F. Delmas and P. Hoscheit. A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces. Electron. J. Probab.18 (2013) 14, 21 pp. (electronic). · Zbl 1285.60004 |

[3] | L. Addario-Berry, N. Broutin and C. Holmgren. Cutting down trees with a Markov chainsaw. Ann. Appl. Probab.24 (6) (2014) 2297-2339. · Zbl 1352.60009 |

[4] | M. Albenque and C. Goldschmidt. The Brownian continuum random tree as the unique solution to a fixed point equation. Electron. Commun. Probab.20 (2015) 61, 14 pp. (electronic). · Zbl 1328.60016 |

[5] | D. Aldous. The continuum random tree. I. Ann. Probab.19 (1) (1991) 1-28. · Zbl 0722.60013 |

[6] | D. Aldous. The continuum random tree II: An overview. In Stochastic Analysis. Cambridge University Press, 1991. · Zbl 0791.60008 |

[7] | D. Aldous. The continuum random tree III. Ann. Probab.21 (1) (1993) 248-289. · Zbl 0791.60009 |

[8] | D. Aldous. Recursive self-similarity for random trees, random triangulations and Brownian excursion. Ann. Probab.22 (2) (1994) 527-545. · Zbl 0808.60017 |

[9] | D. Aldous and J. Pitman. The standard additive coalescent. Ann. Probab.26 (4) (1998) 1703-1726. · Zbl 0936.60064 |

[10] | D. Aldous and J. Pitman. A family of random trees with random edge lengths. Random Structures Algorithms15 (2) (1999) 176-195. · Zbl 0934.05117 |

[11] | D. Aldous and J. Pitman. Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent. Probab. Theory Related Fields118 (4) (2000) 455-482. · Zbl 0969.60015 |

[12] | D. J. Aldous and A. Bandyopadhyay. A survey of max-type recursive distributional equations. Ann. Appl. Probab.15 (2) (2005) 1047-1110. · Zbl 1105.60012 |

[13] | E. Baur and J. Bertoin. Cutting edges at random in large recursive trees. In Stochastic Analysis and Applications 2014 51-76. Springer Proc. Math. Stat.100. Springer, Cham, 2014. · Zbl 1390.60043 |

[14] | J. Bertoin. Self-similar fragmentations. Ann. Inst. Henri Poincaré Probab. Stat.38 (3) (2002) 319-340. · Zbl 1002.60072 |

[15] | J. Bertoin. Fires on trees. Ann. Inst. Henri Poincaré Probab. Stat.48 (4) (2012) 909-921. · Zbl 1263.60083 |

[16] | J. Bertoin. The cut-tree of large recursive trees. Ann. Inst. Henri Poincaré Probab. Stat.51 (2) (2015) 478-488. · Zbl 1351.60010 |

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

[18] | N. H. Bingham, C. M. Goldie and J. L. Teugels. Regular Variation. Encyclopedia of Mathematics and Its Applications27. Cambridge University Press, Cambridge, 1989. |

[19] | N. Broutin and M. Wang. Cutting down \(\mathbf{p} \)-trees and inhomogeneous continuum random trees. Bernoulli23 (4A) (2017) 2380-2433. · Zbl 1388.60036 |

[20] | N. Broutin and M. Wang. Reversing the cut tree of the Brownian continuum random tree. Electron. J. Probab.22 (2017) 80, 23 pp. (electronic). · Zbl 1379.60095 |

[21] | D. Burago, Y. Burago and S. Ivanov. A Course in Metric Geometry. Graduate Studies in Mathematics33. American Mathematical Society, Providence, RI, 2001. · Zbl 0981.51016 |

[22] | M. Camarri and J. Pitman. Limit distributions and random trees derived from the birthday problem with unequal probabilities. Electron. J. Probab.5 (2000) 2, 18 pp. (electronic). · Zbl 0953.60030 |

[23] | E. Crane. Steady state clusters and the Ráth-Tóth mean field forest fire model. Available at arXiv:1809.03462. |

[24] | E. Crane, N. Freeman and B. Tóth. Cluster growth in the dynamical Erdős-Rényi process with forest fires. Electron. J. Probab.20 (2015) 101, 33 pp. (electronic). |

[25] | D. Dieuleveut. The vertex-cut-tree of Galton-Watson trees converging to a stable tree. Ann. Appl. Probab.25 (4) (2015) 2215-2262. · Zbl 1319.60167 |

[26] | M. Drmota, A. Iksanov, M. Moehle and U. Roesler. A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree. Random Structures Algorithms34 (3) (2009) 319-336. · Zbl 1187.05068 |

[27] | T. Duquesne and J.-F. Le Gall. Random Trees, Lévy Processes and Spatial Branching Processes. Asterisque281. SMF, 2002. |

[28] | T. Duquesne and J.-F. Le Gall. Probabilistic and fractal aspects of Lévy trees. Probab. Theory Related Fields131 (4) (2005) 553-603. · Zbl 1070.60076 |

[29] | R. Durrett. Probability: Theory and Examples, 4th edition. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2010. |

[30] | R. Durrett and T. M. Liggett. Fixed points of the smoothing transformation. Z. Wahrsch. Verw. Gebiete64 (3) (1983) 275-301. · Zbl 0506.60097 |

[31] | S. N. Evans, J. Pitman and A. Winter. Rayleigh processes, real trees, and root growth with re-grafting. Probab. Theory Related Fields134 (1) (2006) 81-126. · Zbl 1086.60050 |

[32] | S. N. Evans and A. Winter. Subtree prune and regraft: A reversible real tree-valued Markov process. Ann. Probab.34 (3) (2006) 918-961. · Zbl 1101.60054 |

[33] | J. A. Fill, N. Kapur and A. Panholzer. Destruction of very simple trees. Algorithmica46 (3-4) (2006) 345-366. · Zbl 1106.68081 |

[34] | K. Fukaya. Collapsing of Riemannian manifolds and eigenvalues of Laplace operator. Invent. Math.87 (3) (1987) 517-547. · Zbl 0589.58034 |

[35] | C. Goldschmidt and B. Haas. A line-breaking construction of the stable trees. Electron. J. Probab.20 (2015) 16, 24 pp. (electronic). · Zbl 1409.05054 |

[36] | A. Greven, P. Pfaffelhuber and A. Winter. Convergence in distribution of random metric measure spaces \(( \Lambda \)-coalescent measure trees). Probab. Theory Related Fields145 (1) (2009) 285-322. · Zbl 1215.05161 |

[37] | M. Gromov. Metric Structures for Riemannian and Non-Riemannian Spaces, English edition. Modern Birkhäuser Classics. Birkhäuser Boston, Inc., Boston, MA, 2007. Based on the 1981 French original, With appendices by M. Katz, P. Pansu and S. Semmes, Translated from the French by Sean Michael Bates. |

[38] | B. Haas and G. Miermont. Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees. Ann. Probab.40 (6) (2012) 2589-2666. · Zbl 1259.60033 |

[39] | B. Haas, J. Pitman and M. Winkel. Spinal partitions and invariance under re-rooting of continuum random trees. Ann. Probab.37 (4) (2009) 1381-1411. · Zbl 1181.60128 |

[40] | C. Holmgren. Random records and cuttings in binary search trees. Combin. Probab. Comput.19 (3) (2010) 391-424. · Zbl 1215.05162 |

[41] | 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 |

[42] | S. Janson. Random cutting and records in deterministic and random trees. Random Structures Algorithms29 (2) (2006) 139-179. · Zbl 1120.05083 |

[43] | I. Kortchemski. Invariance principles for Galton-Watson trees conditioned on the number of leaves. Stochastic Process. Appl.122 (9) (2012) 3126-3172. · Zbl 1259.60103 |

[44] | A. Meir and J. W. Moon. Cutting down random trees. J. Aust. Math. Soc.11 (1970) 313-324. · Zbl 0196.27602 |

[45] | A. Meir and J. W. Moon. Cutting down recursive trees. Math. Biosci.21 (1974) 173-181. · Zbl 0288.05102 |

[46] | G. Miermont. Self-similar fragmentations derived from the stable tree. I. Splitting at heights. Probab. Theory Related Fields127 (3) (2003) 423-454. · Zbl 1042.60043 |

[47] | G. Miermont. Self-similar fragmentations derived from the stable tree. II. Splitting at nodes. Probab. Theory Related Fields131 (3) (2005) 341-375. · Zbl 1071.60065 |

[48] | G. Miermont. Tessellations of random maps of arbitrary genus. Ann. Sci. Éc. Norm. Supér. (4)42 (5) (2009) 725-781. · Zbl 1228.05118 |

[49] | A. Panholzer. Cutting down very simple trees. Quaest. Math.29 (2) (2006) 211-227. · Zbl 1120.05020 |

[50] | J. Pitman. Combinatorial stochastic processes. In Lectures from the 32nd Summer School on Probability Theory Held in Saint-Flour, July 7-24, 2002, with a Foreword by Jean Picard. Lecture Notes in Mathematics1875. Springer-Verlag, Berlin, 2006. |

[51] | B. Ráth and B. Tóth. Erdős-Rényi random graphs \(+\) forest fires \(=\) self-organized criticality. Electron. J. Probab.14 (2009) 45, 1290-1327. · Zbl 1197.60093 |

[52] | D. Rizzolo. Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set. Ann. Inst. Henri Poincaré Probab. Stat.51 (2) (2015) 512-532. · Zbl 1319.60170 |

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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.