The Critical Behavior of Random Digraphs
We study the critical behavior of the random digraph D(n, p) for np = 1 + epsilon, where epsilon = epsilon(n) = o(1). We show that if epsilon(3)n -> -infinity, then a.a.s. D(n, p) consists of components which are either isolated vertices or directed cycles, each of size O(p) (|epsilon|(-1)). On the other hand, if epsilon(3)n -> infinity, then a.a.s. the structure of D(n, p) is dominated by the unique complex component of size (4 + o(1))epsilon(2)n, whereas all other components are of size O(p)(epsilon(-1)). (C) 2009 Wiley Periodicals, Inc. Random Struct. Alg., 35, 271-293, 2009
critical behavior random digraphs phase transition