THE STRONG-CONVERGENCE OF MAXIMAL DEGREES IN UNIFORM RANDOM RECURSIVE TREES AND DAGS

We show that the maximal degree in a uniform random recursive tree is almost surely (1 + o(1)) log(2) n. 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)) log(1+1/r) n. (C) 1995 John Wiley and Sons, Inc.