Broadcasting in random recursive dags

Simon Briend, Luc Devroye, Gabor Lugosi

A uniform $k$-{\sc dag} generalizes the uniform random recursive tree by picking $k$ parents uniformly at random from the existing nodes. It starts with $k$ ''roots''. Each of the…