The phase transition in the evolution of random digraphs

Abstract Let \documentclass{article}\pagestyle{empty}\begin{document}$ \mathop {\rm D}\limits^ \to $\end{document} ( n, M ) denote a digraph chosen at random from the family of all digraphs on n vertices with M arcs. We shall prove that if M / n ≤ c < 1 and ω( n ) → ∞, then with probability tending to 1 as n → ∞ all components of \documentclass{article}\pagestyle{empty}\begin{document}$ \mathop {\rm D}\limits^ \to $\end{document} ( n, M ) are smaller than ω( n ), whereas when M / n ≥ c > 1 the largest component of \documentclass{article}\pagestyle{empty}\begin{document}$ \mathop {\rm D}\limits^ \to $\end{document} ( n, M ) is of the order n with probability 1 ‐ o (1).