Premium
A phase transition phenomenon in a random directed acyclic graph
Author(s) -
Pittel B.,
Tungol R.
Publication year - 2001
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/1098-2418(200103)18:2<164::aid-rsa1004>3.0.co;2-h
Subject(s) - combinatorics , mathematics , binary logarithm , random graph , transitive closure , vertex (graph theory) , limiting , graph , discrete mathematics , mechanical engineering , engineering
Let a random directed acyclic graph be defined as being obtained from the random graph G n , p by orienting the edges according to the ordering of vertices. Let γ n * be the size of the largest (reflexive, transitive) closure of a vertex. For p = c (log n )/ n , we prove that, with high probability, γ n * is asymptotic to n c log n , 2 n (log log n )/log n , and n (1−1/ c ) depending on whether c <1, c =1, or c >1. We also determine the limiting distribution of the first vertex closure in all three ranges of c . As an application, we show that the expected number of comparable pairs is asymptotic to n 1+ c / c log n , ½( n (log log n )/log n ) 2 , and ½( n (1−1/ c )) 2 , respectively. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18: 164–184, 2001