Limit distribution for the maximum degree of a random recursive tree

摘要

If a recursive tree is selected uniformly at random from among all recursive trees on n vertices, then the distribution of the maximum in-degree Δ is given asymptotically by the following theorem: for any fixed integer d,Pn(Δ⩽⌊μn⌋+d)=exp(−2{μn}−d−1)+o(1)as n→∞, where μn=log2n. (As usual, ⌊μn⌋ denotes the greatest integer less than or equal to μn, and {μn}=μn−⌊μn⌋.) The proof makes extensive use of asymptotic approximations for the partial sums of the exponential series.