SAMS Subject Classification Number: 6

A directed acyclic graph (DAG) is a digraph with no directed cycles. More formally, a DAG consists of vertices and edges (also called arcs) with each edge directed from one vertex to another in such a way that following those directions will never form a closed loop. These objects are omnipresent in modern science, e.g., they are used as graphical representations of food webs, citation networks, Bayesian networks, etc. We consider a random DAG \(\mathbb{D}_{ac}(n,p)\) which is motivated by the well-known binomial model for undirected graphs. The \(\mathbb{D}_{ac}(n,p)\) model is obtained from the binomial random digraph model \(\mathbb{D}(n,p)\) simply conditioned to be acyclic. We are mainly interested in the sparse regime where \(p\) is of the form \(\frac{\lambda}{n}\) and \(\lambda\) is a fixed positive constant as it is known that these random structures undergo a phase transition around \(p=\frac{1}{n}\).

In the case of general digraphs, it is fundamental to understand the strongly connected components. However, by definition, a strongly connected component of a DAG can only have at most one vertex. Hence, for DAGs it makes sense to consider the weakly connected components instead. An isolated vertex in a digraph can be regarded as a weakly connected component of order one. It was recently proved that the number of isolated vertices in \(\mathbb{D}_{ac}(n,\lambda/n)\) is asymptotically normal with mean linear in \(n\) as \(n\to\infty\). In this talk, we discuss a generalisation of the latter result where we consider the number of weakly components of order bounded by a fixed positive constant. Our approach is analytic which is a combination of symbolic method and complex contour integral techniques.