zbMATH — the first resource for mathematics

Isolating nodes in recursive trees. (English) Zbl 1180.05031
Summary: We consider the number of random cuts that are necessary to isolate the node with label \(\lambda\), \(1 \leq \lambda \leq n\), in a random recursive tree of size \(n\). At each stage of the edge-removal procedure considered an edge is chosen at random from the tree and cut, separating the tree into two subtrees. The procedure is then continued with the subtree containing the specified label \(\lambda \), whereas the other subtree is discarded. The procedure stops when the node with label \(\lambda \) is isolated. Using a recursive approach we are able to give asymptotic expansions for all ordinary moments of the random variable \(X _{n, \lambda ,}\) which counts the number of random cuts required to isolate the vertex with label \(\lambda\) in a random size-\(n\) recursive tree, for small labels, i.e., \(\lambda = l\), and large labels, i.e., \(\lambda = n+1-l\), with \(l \geq 1\) fixed and \(n \to \infty\). Moreover, we can characterize the limiting distribution of a scaled variant of \(X_{n,\lambda}\), for the instance of large labels.

05C05 Trees
05C80 Random graphs (graph-theoretic aspects)
05A16 Asymptotic enumeration
60C05 Combinatorial probability
60F05 Central limit and other weak theorems
Full Text: DOI