Counting directed acyclic and elementary digraphs (Q2199812)

The strongly connected components of directed acyclic graphs (DAGs) are only isolated vertices. Using this fact, the authors discover that when \(m =cn\), where \(m\) is the number of directed edges, \(n\) is the number of vertices, and \(c <1\) is a constant, the asymptotic probability for a random digraph to be acyclic is an explicit function \(p(c) = e^{-c}(1- c)\). When \(m = n(1 + \mu n^{-1/3})\), the asymptotic behavior changes, and the probability for a digraph to be acyclic becomes \(n^{-1/3}C(\mu)\), where \(C(\mu)\) is an explicit function of \(\mu\). \textit{T. Łuczak} and \textit{T. G. Seierstad} [Random Struct. Algorithms 35, No. 3, 271--293 (2009; Zbl 1214.05157)] showed that, as \(\mu \rightarrow -\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, and such digraphs are called elementary digraphs. The present authors also express the probability for a random digraph to be elementary as a function of \(\mu\). These results are obtained using techniques from analytic combinatorics, developed in particular for the study of random graphs.