TY - JOUR
T1 - Sudden emergence of a giant k-core in a random graph
AU - Pittel, Boris
AU - Spencer, Joel
AU - Wormald, Nicholas
N1 - Funding Information:
* Research supported by the Australian Research Council.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 1996/5
Y1 - 1996/5
N2 - The k-core of a graph is the largest subgraph with minimum degree at least k. For the Erdos-Rényi random graph G(n, m) on n vertives, with m edges, it is known that a giant 2-core grows simultaneously with a giant component, that is, when m is close to n/2. We show that for k ≥ 3, with high probability, a giant k-core appears suddenly when m reaches ckn/2; here ck = minλ>0 λ/πk(λ) and πk(λ) = P{Poisson(λ)≥k-1}. In particular, c3≈3.35. We also demonstrate that, unlike the 2-core, when a k-core appears for the first time it is very likely to be giant, of size ≈pk(λk)n. Here λk is the minimum point of λ/πk(λ) and pk(λk) = P{Poisson(λk)≥k}. For k = 3, for instance, the newborn 3-core contains about 0.27n vertices. Our proofs are based on the probabilistic analysis of an edge deletion algorithm that always find a k-core if the graph has one.
AB - The k-core of a graph is the largest subgraph with minimum degree at least k. For the Erdos-Rényi random graph G(n, m) on n vertives, with m edges, it is known that a giant 2-core grows simultaneously with a giant component, that is, when m is close to n/2. We show that for k ≥ 3, with high probability, a giant k-core appears suddenly when m reaches ckn/2; here ck = minλ>0 λ/πk(λ) and πk(λ) = P{Poisson(λ)≥k-1}. In particular, c3≈3.35. We also demonstrate that, unlike the 2-core, when a k-core appears for the first time it is very likely to be giant, of size ≈pk(λk)n. Here λk is the minimum point of λ/πk(λ) and pk(λk) = P{Poisson(λk)≥k}. For k = 3, for instance, the newborn 3-core contains about 0.27n vertices. Our proofs are based on the probabilistic analysis of an edge deletion algorithm that always find a k-core if the graph has one.
UR - http://www.scopus.com/inward/record.url?scp=0030144334&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0030144334&partnerID=8YFLogxK
U2 - 10.1006/jctb.1996.0036
DO - 10.1006/jctb.1996.0036
M3 - Article
AN - SCOPUS:0030144334
VL - 67
SP - 111
EP - 151
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
SN - 0095-8956
IS - 1
ER -