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

2018/04/11 by Mitsche, Dieter, Molloy, Michael, Pralat, Pawel
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1804.04173

Abstract

We prove that G_n,p=c/n whp has a k-regular subgraph if c is at least e^-Θ(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^-Θ(k).

Related

• On the threshold for k-regular subgraphs of random graphs
• The first k-regular subgraph is large
• Sharp thresholds for spanning regular subgraphs
• How does the core sit inside the mantle?
• Sharp thresholds for spanning regular graphs