Centre for Discrete and Applicable Mathematics

CDAM Research Report, LSE-CDAM-2006-13

October 2006

A Simple Solution to the k-Core Problem

Svante Janson and Malwina J. Luczak

We study the $k$-core of a random (multi)graph on $n$ vertices with a given degree sequence. We let \ntoo. Then, under some regularity conditions on the degree sequences, we give conditions on the asymptotic shape of the degree sequence that imply that with high probability the $k$-core is empty, and other conditions that imply that with high probability the $k$-core is non-empty and the sizes of its vertex and edge sets satisfy a law of large numbers; under suitable assumptions these are the only two possibilities. In particular, we recover the result by Pittel, Spencer and Wormald \cite{psw96} on the existence and size of a $k$-core in $G(n,p)$ and $G(n,m)$, see also Molloy~\cite{Molloy05} and Cooper~\cite{c04}.

A PDF file (215 kB) with the full contents of this report can be downloaded by clicking here.

Alternatively, if you would like to get a free hard copy of this report, please send the number of this report, LSE-CDAM-2006-13, together with your name and postal address to:

CDAM Research Reports Series
Centre for Discrete and Applicable Mathematics
London School of Economics
Houghton Street
London WC2A 2AE, U.K.

Phone: +44(0)-20-7955 7494.
Fax: +44(0)-20-7955 6877.
Email: info@maths.lse.ac.uk

		Introduction to the CDAM Research Report Series.
		CDAM Homepage.

		CDAM Research Reports Series Centre for Discrete and Applicable Mathematics London School of Economics Houghton Street London WC2A 2AE, U.K.
		Phone: +44(0)-20-7955 7494. Fax: +44(0)-20-7955 6877. Email: info@maths.lse.ac.uk