Counting strongly connected (k1, k2)‐directed cores

Consider the set of all digraphs on [N] with M edges, whose minimum in‐degree and minimum out‐degree are at least k1 and k2 respectively. For k:=min⁡{k1,k2}≥2 and M/N≥max⁡{k1,k2}+ɛ, M=Θ(N), we show that, among those digraphs, the fraction of k‐strongly connected digraphs is 1−O(N−(k−1)). Earlier wit...

Full description

Saved in:
Bibliographic Details
Published in:Random structures & algorithms 2018-08, Vol.53 (1), p.3-14
Main Author: Pittel, Boris
Format: Article
Language:English
Subjects:
counting cores
digraph
Graph theory
strong connectivity
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Consider the set of all digraphs on [N] with M edges, whose minimum in‐degree and minimum out‐degree are at least k1 and k2 respectively. For k:=min⁡{k1,k2}≥2 and M/N≥max⁡{k1,k2}+ɛ, 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∗(k1,k2) for birth of a giant (k1, k2)‐core in the random digraph D(n,m=[cn]). Combining the claims, for c>c∗(k1,k2) with probability 1−O(N−(k−1)) the giant (k1, k2)‐core exists and is k‐strongly connected.
ISSN:1042-9832
1098-2418
DOI:10.1002/rsa.20759