Birth of a giant $(k_1,k_2)$-core in the random digraph

Abstract

The $(k_1,k_2)$-core of a digraph is the largest sub-digraph with minimum in-degree and minimum out-degree at least $k_1$ and $k_2$ respectively. For $\max \{k_1,k_2\}\ge 2$, we establish existence of the threshold edge-density $c^{\ast }=c^{\ast }(k_1,k_2)$, such that the random digraph $D(n,m)$, on the vertex set $[n]$ with $m$ edges, asymptotically almost surely has a giant $(k_1,k_2)$-core if $m/n>c^{\ast }$, and has no $(k_1,k_2)$-core if $m/n<c^{\ast }$. Specifically, denoting $\text{P}(\text{Poisson}(z)\ge k)$ by $p_k(z)$, we prove that $c^{\ast }=\underset{z_1,z_2}{\min }\max \left\{\frac{z_1}{p_{k_1}(z_1)p_{k_2-1}(z_2)};\frac{z_2}{p_{k_1-1}(z_1)p_{k_2}(z_2)}\right\}$.