pith. sign in

arxiv: 1609.00290 · v1 · pith:EWYRD7JTnew · submitted 2016-09-01 · 🧮 math.CO · math.PR

Counting strongly connected (k₁,k₂)-directed cores

classification 🧮 math.CO math.PR
keywords connecteddigraphsstronglybiglcoregiantminimumbirth
0
0 comments X
read the original 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\}\ge 2$ and $M/N>\max\{k_1,k_2\}$, $M=\Theta(N)$, we show that, among those digraphs, the fraction of $k$-strongly connected digraphs is $1-O\bigl(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=[cn])$. Combining the claims, for $c>c^*(k_1,k_2)$ with probability $1-O\bigl(N^{-(k-1)})$ the giant $(k_1,k_2)$-core exists and is $k$-strongly connected.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.