Counting directed acyclic and elementary digraphs

Abstract

Directed acyclic graphs (DAGs) can be characterised as directed graphs whose strongly connected components are isolated vertices. Using this restriction on the strong 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)$, such that $p(0)=1$ and $p(1)=0$. When $m=n(1+\mu n^{-1/3})$, the asymptotic behaviour changes, and the probability that a digraph is acyclic becomes $n^{-1/3}C(\mu )$, where $C(\mu )$ is an explicit function of $\mu$. Łuczak and Seierstad (2009, Random Structures & Algorithms, 35(3), 271--293) showed that, as $\mu \to -\infty$, the strongly connected components of a random digraph with $n$ vertices and $m=n(1+\mu 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 $\mu$. Those results are obtained using techniques from analytic combinatorics, developed in particular to study random graphs.

10 pages; Accepted to FPSAC. Updated in accordance with the comments of reviewers