k-regular subgraphs near the k-core threshold of a random graph

Abstract

We prove that $G_{n,p=c/n}$ whp has a $k$-regular subgraph if $c$ is at least $e^{-\Theta (k)}$ above the threshold for the appearance of a subgraph with minimum degree at least $k$; i.e. an non-empty $k$-core. In particular, this pins down the threshold for the appearance of a $k$-regular subgraph to a window of size $e^{-\Theta (k)}$.