Birth of a giant (k₁,k₂)-core in the random digraph

2016/08/17 by Pittel, Boris, Poole, Dan
#05C05 #05C30 #05C80 #34E05 #60C05 #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR)

paper · doi:10.48550/arxiv.1608.05095

Abstract

The (k₁,k₂)-core of a digraph is the largest sub-digraph with minimum in-degree and minimum out-degree at least k₁ and k₂ respectively. For max\k₁, k₂\ ≥ 2, we establish existence of the threshold edge-density c^*=c^*(k₁,k₂), such that the random digraph D(n,m), on the vertex set [n] with m edges, asymptotically almost surely has a giant (k₁,k₂)-core if m/n> c^*, and has no (k₁,k₂)-core if m/n

Related

• Counting strongly connected (k₁,k₂)-directed cores
• A simple solution to the k-core problem
• On the threshold for k-regular subgraphs of random graphs
• How does the core sit inside the mantle?
• k-regular subgraphs near the k-core threshold of a random graph