Counting strongly connected (k1, k2)‐directed cores. Issue 1 (29th December 2017) - Pittel, Boris
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.