The number of descendants in a random directed acyclic graph
share
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≥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/√(n) converges in distribution; the limit distribution is, up to a constant factor, given by the dth root of a Gamma distributed variable. Γ(d/(d-1)). When d=2, the limit distribution can also be described as a chi distribution χ(4). We also show convergence of moments, and find thus the asymptotics of the mean and higher moments.
READ FULL TEXT