Birth of a giant (k₁,k₂)-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

m a x k_{1}, k_{2} g e q 2

, we establish existence of the threshold edge-density

c^{*} = c^{*} (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^{*}

, and has no

(k_{1}, k_{2})

-core if

m / n < c^{*}

. Specifically, denoting

e x t P (e x t P o i s s o n (z) g e k)

by

p_{k} (z)

, we prove that

c^{*} = m i n l i m i t s_{z_{1}, z_{2}} m a x l e f t f r a c z_{1} p_{k_{1}} (z_{1}) p_{k_{2} - 1} (z_{2}); f r a c z_{2} p_{k_{1} - 1} (z_{1}) p_{k_{2}} (z_{2}) i g h t

.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: Birth of a giant \((k_{1},k_{2})\)-core in the random digraph