The critical behavior of random digraphs

We study the critical behavior of the random digraph D ( n , p ) for n p = 1 + ε, where ε = ε( n ) = o (1). We show that if ε 3 n →—∞, then a.a.s. D ( n , p ) consists of components which are either isolated vertices or directed cycles, each of size O p (|ε| −1 ). On the other hand, if ε 3 n → ∞ , then a.a.s. the structure of D ( n , p ) is dominated by the unique complex component of size (4 + o (1))ε 2 n , whereas all other components are of size O p (ε −1 ). © 2009 Wiley Periodicals, Inc. Random Struct. Alg., 2009