On the threshold for k-regular subgraphs of random graphs

2007/06/08 by Pawel Pralat, Pralat, Pawel, Jacques Verstraete +3
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Probability (math.PR) #math.CO #math.PR

paper · pdf · doi:10.48550/arxiv.0706.1103

arxiv created 2007/06/08 · arxiv updated 2009/12/01

Abstract

The k-core of a graph is the largest subgraph of minimum degree at least k. We show that for k sufficiently large, the (k + 2)-core of a random graph \G(n,p) asymptotically almost surely has a spanning k-regular subgraph. Thus the threshold for the appearance of a k-regular subgraph of a random graph is at most the threshold for the (k+2)-core. In particular, this pins down the point of appearance of a k-regular subgraph in \G(n,p) to a window for p of width roughly 2/n for large n and moderately large k.

Related

• k-regular subgraphs near the k-core threshold of a random graph
• The first k-regular subgraph is large
• A simple solution to the k-core problem
• Birth of a giant (k₁,k₂)-core in the random digraph
• Sharp thresholds for spanning regular subgraphs