PC Seminar: The number of descendants in a random directed acyclic graph

Abstract: Consider a random directed acyclic graph, obtained by recursively adding vertices, where each new vertex has a fixed outdegree $d$ and the endpoints of the $d$ edges from it are chosen uniformly at random among previously existing vertices. For simplicity we assume $d=2$.

We study the set of vertices that are descendants of a given vertex $n$ (asymptotically, for large $n$). The main result is that the number of such vertices, divided by $\sqrt{n}$, converges in distribution together with all moments. The limit distribution is, up to a constant factor, a chi distribution $\chi(4)$.

The talk is based on a recent preprint arXiv:2302.12467 or my web page.

This is a seminar in our seminar series on Probability and Combinatorics (PC).