SUDDEN EMERGENCE OF A GIANT K-CORE IN A RANDOM GRAPH

The k-core of a graph is the largest subgraph with minimum degree at l east k. For the Erdos-Renyi random graph G(n, m) on n vertiv;es, with In 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 g reater than or equal to 3, with high probability, a giant k-core appea rs suddenly when m reaches c(k)n/2; here c(k) = min<(lambda>>0)lambda/ pi(k)(lambda) and pi(k)(lambda) = P{Poisson(lambda) greater than or eq ual to k -1}. In particular, c(3) approximate to 3.35. We also demonst rate that, unlike the 2-core. when a k-core appears for the first time it is very likely to be giant, of size approximate to p(k)(lambda(k)) n. Here lambda(k) is the minimum point of lambda/pi(k)(lambda) and p(k )(lambda(k))= P{Poisson(lambda(k)) greater than or equal to k}. For k = 3, for instance, the newborn 3-core contains about 0.27n vertices. O ur proofs are based on the probabilistic analysis of an edge deletion algorithm that always find a k-core if the graph has one. (C) 1996 Aca demic Press, Inc.