A simple solution to the k-core problem

Abstract

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 on the existence and size of a k-core in G(n,p) and G(n,m). Our method is based on the properties of empirical distributions of independent random variables, and leads to simple proofs.

14 pages

Cited by in corpus (7)

• Asymptotic normality of the $k$-core in random graphs
• The diameter of weighted random graphs
• How to determine if a random graph with a fixed degree sequence has a giant component
• Cores of random graphs are born Hamiltonian
• Poisson Cloning Model for Random Graphs
• I/O Efficient Core Graph Decomposition at Web Scale
• On the threshold for k-regular subgraphs of random graphs