Destruction of recursive trees
If a randomly chosen edge is removed from one of the \((n- 1)!\) recursive trees \(T\) with \(n\) labelled vertices, then \(T\) falls into two subtrees one of which contains the root vertex with label 1. Suppose we continue to remove edges from the successively smaller subtrees that contain the root. \textit{A. Meir} and \textit{J. W. Moon} [Math. Biosci. 21, 173--181 (1974; Zbl 0288.05102)] determined the expected number of edges that are removed before the root is isolated and the process stops. The author of the present paper introduces a cost \(c_m= m^\alpha\), \(\alpha\geq 0\), associated with removing an edge from a recursive tree with \(m\) vertices. He considers the procedure just described and a related procedure in which the edge-removing process is applied to all subtrees encountered and terminates when all edges have been removed. He determines the asymptotic behaviour of the \(s\)th moment and the \(s\)th centered moment of the total costs incurred before these two processes terminate, for any fixed positive integer \(s\). In particular, the expected value of the total cost for both procedures is asymptotic to \(n^{\alpha+ 1}/(\alpha+ 1)\log n\), where we assume that \(\alpha> 0\) in the case of the second procedure. For the entire collection see [Zbl 1047.68003].
- Isolating the most recent entry in a random recursive tree by random cuts
- A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
- Isolating a leaf in rooted trees via random cuttings
- Isolating nodes in recursive trees
- Destruction of very simple trees
- Multiple isolation of nodes in recursive trees
- Uniform recursive trees: branching structure and simple random downward walk
- Cutting down trees with a Markov chainsaw
- scientific article; zbMATH DE number 1399917
- Cut trees in the topological analysis of branching patterns
- The \(k\)-cut model in deterministic and random trees
- The cut-tree of large recursive trees
- Asymptotic results concerning the total branch length of the Bolthausen-Sznitman coalescent
- A class of random recursive tree algorithms with deletion
- Breakage and restoration in recursive trees
- A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
- On asymptotics of the beta coalescents
- Asymptotic hitting probabilities for the Bolthausen-Sznitman coalescent
- On Asymptotics of Exchangeable Coalescents with Multiple Collisions
- On the number of collisions in beta(2, b)-coalescents
- On the block counting process and the fixation line of the Bolthausen-Sznitman coalescent
- Quenched worst-case scenario for root deletion in targeted cutting of random recursive trees
- Size distribution of clusters in site-percolation on random recursive tree
- Destruction of very simple trees
This page was built for publication: Destruction of recursive trees
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3154689)