A phase transition phenomenon in a random directed acyclic graph

✍ Scribed by B. Pittel; R. Tungol

• Publisher: John Wiley and Sons
• Year: 2001
• Tongue: English
• Weight: 158 KB
• Volume: 18
• Category: Article
• ISSN: 1042-9832
• DOI: 10.1002/1098-2418(200103)18:2<164::aid-rsa1004>3.0.co;2-h

✦ Synopsis

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, 2n 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, 1 2 n log log n / log n 2 , and 1

2 n 1 -1/c 2 , respectively.