The cut-tree of large recursive trees
The cut-tree of large recursive trees
复制标题
大型递归树的割树
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
J. Bertoin
中科院分区：
文献类型：
--
作者：
J. Bertoin
想象一下，一个图通过以统一的随机顺序一个接一个地切割它的边而逐渐被破坏。所谓的砍伐树记录了这一销毁过程的关键步骤。它可以看作是一个具有自然概率质量的随机度量空间。在这项工作中，我们证明了大小为n的随机递归树的割树在格罗莫夫Hausdorff-Prokhorov意义下以n−1 lnn重标度的概率收敛到赋予通常距离和Lebesgue值的单位区间上.这使得我们能够解释和推广Kuba和Panholzer[15]关于随机递归树中节点的多重隔离的一些最新结果。
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 GromovHausdorff-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 [15] on multiple isolation of nodes in random recursive trees.