A phase transition phenomenon in a random directed acyclic graph (Q2712580)

The size of the largest closure of a vertex in a random directed acyclic graph is studied. A random directed acyclic graph is obtained from a random graph \(G_{n,p}\) by orienting the edges according to the ordering of vertices. The (reflexive, transitive) closure of vertex \(i\) is the number of vertices reachable through a directed path from \(i\) (including vertex \(i\) itself). The size is denoted as \(\gamma_n^{\ast}(i)\), and \(\gamma_n^{\ast}\max_{1\leq i\leq n}\gamma_n^{\ast}(i)\) denotes the maximum size. For \(p=c\log n/n\) with a constant \(c\) the limit behaviour of \(\gamma_n^{\ast}(1)\) and \(\gamma_n^{\ast}\) is derived. The behaviour depends substantially on the value of \(c\). In particular, it is proved that with high probability \(\gamma_n^{\ast}\) is asymptotic to \(n^{c}\log n\), \(2n(\log\log n)/\log n\), and \(n(1-1/c)\) depending on whether \(c<1\), \(c=1\), or \(c>1\).