Premium
The critical behavior of random digraphs
Author(s) -
Łuczak Tomasz,
Seierstad Taral Guldahl
Publication year - 2009
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20283
Subject(s) - digraph , combinatorics , struct , mathematics , random graph , component (thermodynamics) , discrete mathematics , physics , computer science , graph , thermodynamics , programming language
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