Isolating the most recent entry in a random recursive tree by random cuts
A tree \(T\) with \(n\) nodes labelled \(1,2,\dots,n\) is a recursive tree (with node 1 as the root) if for each \(k\) between 2 and \(n\) the labels of the nodes in the path from node 1 to node \(k\) form an increasing sequence. If an edge is removed from one of the \((n-1)!\) recursive trees \(T\) with \(n\) nodes, then \(T\) falls into two subtrees one of which contains node \(n\). If we continue to remove edges from the successively smaller subtrees that contain node \(n\) we eventually isolate node \(n\). Let \(\mu(n)\) and \(\sigma^2(n)\) denote the mean and variance of the number of randomly chosen edges removed from a random recursive tree with \(n\) nodes before isolating node \(n\). The authors show that \(\mu(n)\sim n/2\log n\) and that \(\sigma^2(n)= O(\mu^2(n))\). The analogous problem in which the object is to isolate the root node was considered by \textit{A. Meir} and \textit{J. W. Moon} [Math. Biosc. 21, 173--181 (1974; Zbl 0288.05102)].
- Isolating nodes in recursive trees
- Multiple isolation of nodes in recursive trees
- A probabilistic proof of a weak limit law for the number of cuts needed to isolate the root of a random recursive tree
- A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
- The cut-tree of large recursive trees
- A Probability Model of a Pyramid Scheme
- Cutting down recursive trees
- Distribution of nodes of a tree by degree
- First-passage percolation on the random graph
- scientific article; zbMATH DE number 1409903 (Why is no real title available?)
- scientific article; zbMATH DE number 3340110 (Why is no real title available?)
- scientific article; zbMATH DE number 3400923 (Why is no real title available?)
- scientific article; zbMATH DE number 3049368 (Why is no real title available?)
- Note on the outdegree of a node in random recursive trees
- On the covariance of the level sizes in random recursive trees
- Multiple isolation of nodes in recursive trees
- scientific article; zbMATH DE number 2127740 (Why is no real title available?)
- A limiting distribution for the number of cuts needed to isolate the root of a random recursive tree
- Cutting edges at random in large recursive trees
- Quenched worst-case scenario for root deletion in targeted cutting of random recursive trees
This page was built for publication: Isolating the most recent entry in a random recursive tree by random cuts
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1885072)
