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^{- T h e t a (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^{- T h e t a (k)}

.

Cites Work

Cited In (2)

This page was built for publication: \(k\)-regular subgraphs near the \(k\)-core threshold of a random graph