Key points are not available for this paper at this time.
Thek-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 (λ) =PPoisson (λ) ⩾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) =PPoisson (λ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.
Pittel et al. (Wed,) studied this question.