Premium
The strong convergence of maximal degrees in uniform random recursive trees and dags
Author(s) -
Devroye Luc,
Lu Jiang
Publication year - 1995
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.3240070102
Subject(s) - mathematics , combinatorics , directed acyclic graph , random graph , degree (music) , graph , binary logarithm , tree (set theory) , discrete mathematics , directed graph , convergence (economics) , physics , acoustics , economics , economic growth
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 i th 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 .