The number of descendants in a random directed acyclic graph

Abstract

We consider a well known model of random directed acyclic graphs of order $n$, obtained by recursively adding vertices, where each new vertex has a fixed outdegree $d\ge 2$ and the endpoints of the $d$ edges from it are chosen uniformly at random among previously existing vertices. Our main results concern the number $X$ of vertices that are descendants of $n$. We show that $X/\sqrt{n}$ converges in distribution; the limit distribution is, up to a constant factor, given by the $d$th root of a Gamma distributed variable. $\Gamma (d/(d-1))$. When $d=2$, the limit distribution can also be described as a chi distribution $\chi (4)$. We also show convergence of moments, and find thus the asymptotics of the mean and higher moments.

31 pages. v2: bad typo corrected