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/3C(μ), 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: