Quenched worst-case scenario for root deletion in targeted cutting of random recursive trees

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 the decreasing order of their degrees; namely, let (v⁽ⁱ⁾)ᵢ₌₁ⁿ be such that (v⁽¹⁾) ≥ ⋯ ≥ (v⁽ⁿ⁾) . The targeted vertex-cutting process is performed by sequentially removing vertices v⁽¹⁾, v⁽²⁾, …, v⁽ⁿ⁾ 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, Kₙ , is upper bounded by Z≥ D , which denotes the number of vertices that have degree at least as large as the degree of the root. We prove that ln Z≥ D grows as ln n asymptotically and obtain its limiting behavior in probability. Moreover, we obtain that the k th moment of ln Z≥ D is proportional to (\!ln n)ᵏ . As a consequence, we obtain that the first-order growth of Kₙ is upper bounded by n1-ln 2 , which is substantially smaller than the required number of removals if, instead, the vertices were selected uniformly at random.