A simple solution to the $k$-core problem

Опубликовано 7 сентября 2016, 16:42

We study the $k$-core of a random (multi) graph on $n$ vertices with a given degree sequence. We let $n$ tend to infinity. 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}. Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs. This is joint work with Svante Janson.