An exact threshold theorem for random graphs and the node-packing problem (Q1095150)

The random digraph \(D_ n(m)\) has a uniform probability distribution on the set of digraphs having n nodes, no loops, and constant outdegrees m. An undirected graph \(G_ n(m)\) is obtained by deleting orientations and coalescing muliple edges. It is shown that \(G_ n(m)\) is bicritical as \(n\to \infty\) with a probability tending to 0 for \(m=1\), \((1-2e^{- 2})^{1/2}\) for \(m=2\), and 1 for \(m\geq 3\).