The Phase Transitions in Directed Acyclic Graphs
In this presentation, we will discuss the phase transition in directed acyclic graphs. We propose a random DAG model, Dac(n,p) (where p = λ/n), on the vertex set [n] = {1, 2, …, n}, which was naturally defined as the binomial digraph model D(n,p) conditioned to be acyclic. This DAG model was analyzed using analytic methods such as generating functions and the saddle point method. The first part of our study focuses on the number of occurrences of components with lower excess, namely polytrees and unicyclic DAG components. We prove that the number of polytrees of a fixed size as components of Dac(n,p) has an expectation linear in n and is asymptotically normally distributed. Moreover, the number of occurrences of unicyclic DAG components has a bounded expectation with an asymptotically Poisson distribution. Furthermore, we prove that small components of higher excess do not occur with probability tending to 1. We observe that a phase transition occurs at λ = 1/2. In particular, we show that for λ < 1/2, the probability that Dac(n,p) consists entirely of polytree and unicyclic DAG components approaches 1 as n approaches infinity. In contrast, for λ > 1/2, this probability goes to zero exponentially fast in n. We also look at the number of edges in Dac(n,p) and prove that a sudden change occurs at λ = 1.