The strong convergence of maximal degrees in uniform random recursive trees and dags
Luc Devroye, Lu Jiang · Random Structures and Algorithms · 1995
Abstract We show that the maximal degree in a uniform random recursive tree is almost surely (1 + o(1)) log2n. A random directed acyclic graph on n nodes is defined by connecting the ith node for each i > m with r of its predecessors uniformly and at random. The maximal degree is shown to be almost surely (1 + o(1))log1+1/rn.