Sudden Emergence of a Giantk-Core in a Random Graph

AbstractThek-core of a graph is the largest subgraph with minimum degree at leastk. For the Erdős–Rényi random graphG(n, m) onnvertives, withmedges, it is known that a giant 2-core grows simultaneously with a giant component, that is, whenmis close ton/2. We show that fork⩾3, with high probability, a giantk-core appears suddenly whenmreachesckn/2; hereck=minλ>0λ/πk(λ) andπk(λ)=P{Poisson(λ)⩾k−1}. In particular,c3≈3.35. We also demonstrate that, unlike the 2-core, when ak-core appears for the first time it is very likely to be giant, of size ≈pk(λk)n. Hereλkis the minimum point ofλ/πk(λ) andpk(λk)=P{Poisson(λk)⩾k}. Fork=3, for instance, the newborn 3-core contains about 0.27nvertices. Our proofs are based on the probabilistic analysis of an edge deletion algorithm that always find ak-core if the graph has one