On the number of vertices of a~random acyclic digraph

V. A. Liskovets

Teoriâ veroâtnostej i ee primeneniâ, Tome 20 (1975) no. 2, pp. 412-420

Résumé

An acyclic digraph is a digraph without directed circuits. Unlike the similar class of non-directed graphs which are called trees, random acyclic digraphs have been hardly studied. Here we are concerned with a rather simple property of them. A vertex of a digraph is called maximal if there are no arcs entering it. Any finite non-empty acyclic digraph has a maximal vertex. Let $\xi_n$ be the number of maximal vertices in a graph chosen at random from the set of all acyclic digraphs without multiple arcs with $n$ given vertices. The main result provides the limit distribution of $\xi_n$ as $n\to\infty$: it is proved to be a discrete probability distribution with the generating function $\alpha(a(1-z))$ where $$ \alpha(z)=\sum_{n=0}^\infty\frac{(-1)^nz^n}{n!2^{n(n-1)/2}} $$ and $a$ is the least real root of $\alpha(z)=0,$ $a1,5$. In particular, $\lim\mathbf M\xi_n=a$, $\lim\mathbf D\xi_n=a(1-a/2)$.