#####
Séminaire Lotharingien de Combinatoire, 84B.2 (2020), 12 pp.

# Élie de Panafieu and Sergey Dovgal

# Counting Directed Acyclic and Elementary Digraphs

**Abstract.**
Directed acyclic graphs (DAGs) can be characterized as directed graphs whose
strongly connected components are isolated vertices. Using this restriction on
the strongly connected components, we discover that when *m* = *cn*,
where *m* is the number of
directed edges, *n* is the number of vertices, and *c* < 1,
the asymptotic
probability that a random digraph is acyclic is an explicit
function *p*(*c*) = *e*^{-c}(1-*c*).
When *m* = *n*(1+μ*n*^{-1/3}), the
asymptotic behaviour changes, and the probability that a digraph is acyclic
becomes *n*^{-1/3}*C*(μ),
where *C*(μ) is an explicit function of μ.
In 2009, Łuczak and Seierstad
showed that, as μ -> -*\infty*, the strongly
connected components of a random digraph with *n* vertices and *m* = *n*(1+μ*n*^{-1/3}) directed edges
are, with high probability, only isolated vertices and cycles. We call such
digraphs elementary digraphs. We express the probability that a random digraph
is elementary as a function of μ.
Those results are obtained using techniques from analytic combinatorics,
developed in particular to study random graphs.

Received: November 20, 2019.
Accepted: February 20, 2020.
Final version: April 30, 2020.

The following versions are available: