Counting strongly connected (k1, k2)‐directed cores. Issue 1 (29th December 2017)

• Record Type: Journal Article
• Authors: Pittel, Boris
• Is Part Of: Random structures & algorithms. Volume 53:Issue 1(2018)
• Page Start: 3
• Page End: 14
• Publication Date: 2017-12-29
• Subjects: counting cores -- digraph -- strong connectivity; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20759
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract : Consider the set of all digraphs on [ N ] with M edges, whose minimum in‐degree and minimum out‐degree are at least k 1 and k 2 respectively. For k : = min ⁡ { k 1, k 2 } ≥ 2 and M / N ≥ max ⁡ { k 1, k 2 } + ɛ, M = Θ ( N ), we show that, among those digraphs, the fraction of k ‐strongly connected digraphs is 1 − O ( N − ( k − 1 ) ) . Earlier with Dan Poole we identified a sharp edge‐density threshold c ∗ ( k 1, k 2 ) for birth of a giant ( k 1, k 2 )‐core in the random digraph D ( n, m = [ c n ] ) . Combining the claims, for c > c ∗ ( k 1, k 2 ) with probability 1 − O ( N − ( k − 1 ) ) the giant ( k 1, k 2 )‐core exists and is k ‐strongly connected.