Targeted cutting of random recursive trees

MaRDI QIDQ6419161zbMATH OpenFDO

Authors Laura Eslava, Sergio I. López, M. Ortíz

Publication date 30 November 2022

Abstract: We propose a method for cutting down a random recursive tree that focuses on its higher degree vertices. Enumerate the vertices of a random recursive tree of size $n$ according to a decreasing order of their degrees; namely, let $(v^{(i)}{)}_{i=1}^n$ be so that $deg(v^{(1)})geqcdotsgeqdeg(v^{(n)})$. The targeted, vertex-cutting process is performed by sequentially removing vertices $v^{(1)}$, $v^{(2)},ldots,v^{(n)}$ and keeping only the subtree containing the root after each removal. The algorithm ends when the root is picked to be removed. The total number of steps for this procedure, $X_n^{targ}$, is upper bounded by $Z_{geqD}$, which denotes the number of vertices that have degree at least as large as the degree of the root. We obtain that the first order growth of $X_n^{targ}$ is upper bounded by $n^{1-ln2}$, which is substantially smaller than the required number of removals if, instead, the vertices where selected uniformly at random. More precisely, we prove that $ln(Z_{geqD})$ grows as $ln(n)$ asymptotically and obtain its limiting behavior in probability. Moreover, we obtain that the $k$-th moment of $ln(Z_{geqD})$ is proportional to $(ln(n){)}^k$.

This page was built for publication: Targeted cutting of random recursive trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6419161)