Inverting the cut-tree transform

DOI10.1214/18-AIHP921MaRDI QIDQ2337828zbMATH OpenOpenAlexFDO

Authors Louigi Addario-Berry, Daphné Dieuleveut, Christina Goldschmidt

Publication date 20 November 2019

Published in Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1606.04825, https://projecteuclid.org/euclid.aihp/1569398872

zbMATH Keywords

\( \mathbb{R} \)-treecut-treefragmentation

Mathematics Subject Classification ID

Trees (05C05) Combinatorial probability (60C05) Stable stochastic processes (60G52) Branching processes (Galton-Watson, birth-and-death, etc.) (60J80)

Abstract: We consider fragmentations of an R-tree $T$ driven by cuts arriving according to a Poisson process on $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 Bertoin and Miermont for a fragmentation of the Brownian continuum random tree. The cut-tree was generalised by Dieuleveut to a fragmentation of the $alpha$-stable trees, $alphain(1,2)$, and by Broutin and Wang to the inhomogeneous continuum random trees of Aldous and Pitman. Remarkably, in all of these cases, the law of the cut-tree is the same as that of the original R-tree. In this paper, we develop a clean general framework for the study of cut-trees of R-trees. We then focus particularly on the problem of reconstruction: how to recover the original R-tree from its cut-tree. This has been studied in the setting of the Brownian CRT by Broutin and Wang, where they 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 R-trees. We then show that, for the case of the Brownian CRT and the $alpha$-stable trees with $alphain(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.

Recommendations

• Reversing the cut tree of the Brownian continuum random tree
• Cutting down \(\mathbf{p}\)-trees and inhomogeneous continuum random trees
• Self-similar fragmentations derived from the stable tree. II: Splitting at nodes
• The cut-tree of large trees with small heights
• The cut-tree of large Galton-Watson trees and the Brownian CRT

Cites work

• A course in metric geometry
• A family of random trees with random edge lengths
• A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
• A line-breaking construction of the stable trees
• A note on the Gromov-Hausdorff-Prokhorov distance between (locally) compact metric measure spaces
• A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
• A survey of max-type recursive distributional equations
• Cluster growth in the dynamical Erdős-Rényi process with forest fires
• Collapsing of Riemannian manifolds and eigenvalues of Laplace operator
• Combinatorial stochastic processes. Ecole d'Eté de Probabilités de Saint-Flour XXXII -- 2002.
• Convergence in distribution of random metric measure spaces (\(\Lambda \)-coalescent measure trees)
• Cutting down \(\mathbf{p}\)-trees and inhomogeneous continuum random trees
• Cutting down random trees
• Cutting down recursive trees
• Cutting down trees with a Markov chainsaw
• Cutting down very simple trees
• Cutting edges at random in large recursive trees
• Destruction of very simple trees
• Erdős-Renyi random graphs \(+\) forest fires \(=\) self-organized criticality
• Fires on trees
• Fixed points of the smoothing transformation
• scientific article; zbMATH DE number 19286 (Why is no real title available?)
• scientific article; zbMATH DE number 1859371 (Why is no real title available?)
• Inhomogeneous continuum random trees and the entrance boundary of the additive coalescent
• Invariance principles for Galton-Watson trees conditioned on the number of leaves
• Limit distributions and random trees derived from the birthday problem with unequal probabilities
• Probabilistic and fractal aspects of Lévy trees
• Probability. Theory and examples.
• Random cutting and records in deterministic and random trees
• Random records and cuttings in binary search trees
• Rayleigh processes, real trees, and root growth with re-grafting
• Recursive self-similarity for random trees, random triangulations and Brownian excursion
• Reversing the cut tree of the Brownian continuum random tree
• Scaling limits of Markov branching trees and Galton-Watson trees conditioned on the number of vertices with out-degree in a given set
• Scaling limits of Markov branching trees with applications to Galton-Watson and random unordered trees
• Self-similar fragmentation derived from the stable tree. I: Splitting at heights
• Self-similar fragmentations
• Self-similar fragmentations derived from the stable tree. II: Splitting at nodes
• Spinal partitions and invariance under re-rooting of continuum random trees
• Subtree prune and regraft: a reversible real tree-valued Markov process
• Tessellations of random maps of arbitrary genus
• The Brownian continuum random tree as the unique solution to a fixed point equation
• The continuum random tree. I
• The continuum random tree. III
• The cut-tree of large Galton-Watson trees and the Brownian CRT
• The cut-tree of large recursive trees
• The forest associated with the record process on a Lévy tree
• The standard additive coalescent
• The vertex-cut-tree of Galton-Watson trees converging to a stable tree

Cited in

(5)

• Cutting down \(\mathbf{p}\)-trees and inhomogeneous continuum random trees
• Reversing the cut tree of the Brownian continuum random tree
• A recursive distributional equation for the stable tree
• Coupling Bertoin's and Aldous-Pitman's representations of the additive coalescent
• Pruning, cut trees, and the reconstruction problem

This page was built for publication: Inverting the cut-tree transform

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2337828)