Consider the set of all digraphs on @math with @math edges, whose minimum in-degree and minimum out-degree are at least @math and @math respectively. For @math and @math , @math , we show that, among those digraphs, the fraction of @math -strongly connected digraphs is @math . Earlier with Dan Poole we identified a sharp edge-density threshold @math for birth of a giant @math -core in the random digraph @math . Combining the claims, for @math with probability @math the giant @math -core exists and is @math -strongly connected.
The deletion algorithm delivers a sequence @math where @math , and each @math , where for all @math , @math if and only if @math . The @math pairs mark the locations @math in the original @math whose vertex occupants have been deleted after @math steps. The process @math is obviously Markov, though the complexity of its sample space makes it intractable. Let @math be a @math -tuple whose components are the counts of vertices that are in out-light, in-light out-heavy, in-heavy out-light, in-heavy out-heavy, and the total count of all edges in @math . We need that many components since, to preserve Markovian property, we have to classify the in-light degrees and the out-light degrees according to their possible @math and @math values. Fortunately no similar classification is needed for the in-heavy degrees and the out-heavy degrees. It was proved in @cite_15 that the process @math is indeed Markov, and that, conditioned on @math , the sequence @math is uniform.
@cite_15
2517839992
The @math -core of a digraph is the largest sub-digraph with minimum in-degree and minimum out-degree at least @math and @math respectively. For @math , we establish existence of the threshold edge-density @math , such that the random digraph @math , on the vertex set @math with @math edges, asymptotically almost surely has a giant @math -core if @math , and has no @math -core if @math . Specifically, denoting @math by @math , we prove that @math .