A degree-biased cutting process for random recursive trees

Laura Eslava, Sergio I. López, Marco L. Ortiz

Published 2024-08-09Version 1

We study a degree-biased cutting process on random recursive trees, where vertices are deleted with probability proportional to their degree. We verify the splitting property and explicitly obtain the distribution of the number of vertices deleted by each cut. This allows us to obtain a recursive formula for Kn, the number of cuts needed to destroy a random recursive tree of size n. Furthermore, we show that Kn is stochastically dominated by Jn, the number of jumps made by a certain random walk with a barrier. We obtain a convergence in distribution of Jn to a Cauchy random variable. We also explore the relationship of this cutting procedure to a coalescing process and show that the coalescing rate cannot correspond to a {\Lambda}-coalescent since it fails consistency conditions.