Degree distribution in the lower levels of the uniform recursive tree

Abstract

In this note we consider the $k$th level of the uniform random recursive tree after $n$ steps, and prove that the proportion of nodes with degree greater than $t\log n$ converges to $(1-t{)}^k$ almost surely, as $n\to \infty$, for every $t\in (0,1)$. In addition, we show that the number of degree $d$ nodes in the first level is asymptotically Poisson distributed with mean 1; moreover, they are asymptotically independent for $d=1,2,...$.

8 pages

References in corpus (1)

• Emergence of scaling in random networks