Séminaire Lotharingien de Combinatoire, 84B.2 (2020), 12 pp.
Élie de Panafieu and Sergey Dovgal
Counting Directed Acyclic and Elementary Digraphs
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,
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
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: