论文标题
有针对性的随机递归树木
Targeted cutting of random recursive trees
论文作者
论文摘要
我们提出了一种切割一棵随机递归树的方法，该树专注于其更高程度的顶点。根据其学位的降低顺序，列举了大小$ n $的随机递归树的顶点；也就是说，让$（v^{（i）}）_ {i = 1}^{n} $是$ deg（v^{（1）}）\ geq \ cdots \ geq deg（v^{（n）}）$。通过顺序删除顶点$ v^{（1）} $，$ v^{（2）}，\ ldots，v^{（n）} $，并仅保留每个删除后的子树。当选择根以去除根时，算法结束。此过程的步骤总数为$ x_n^{targ} $，由$ z _ {\ geq d} $限制，这表示至少具有与根的程度一样大的顶点。我们获得$ x_n^{targ} $的一阶增长由$ n^{1- \ ln 2} $限制，如果在随机选择的那些均匀选择的顶点时，它大大小于所需的删除数量。更确切地说，我们证明$ \ ln（z _ {\ geq d}）$以$ \ ln（n）$非差异而生长，并以概率获得其限制行为。此外，我们得到$ \ ln（z _ {\ geq d}）$的$ k $ 3钟与$（\ ln（n））^k $成比例。
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)}) \geq \cdots \geq deg (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_{\geq 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_{\geq D})$ grows as $\ln(n)$ asymptotically and obtain its limiting behavior in probability. Moreover, we obtain that the $k$-th moment of $\ln(Z_{\geq D})$ is proportional to $(\ln(n))^k$.
