Targeted cutting of random recursive trees

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)})\ge \cdots \ge deg(v^{(n)})$. The targeted, vertex-cutting process is performed by sequentially removing vertices $v^{(1)}$, $v^{(2)},\dots ,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_{\ge D}$, 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-\ln 2}$, 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_{\ge D})$ grows as $\ln (n)$ asymptotically and obtain its limiting behavior in probability. Moreover, we obtain that the $k$-th moment of $\ln (Z_{\ge D})$ is proportional to $(\ln (n){)}^k$.

13 pages