The first k-regular subgraph is large

2013/03/21 by Gao, Pu
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1303.5139

Abstract

We prove that for sufficiently large k, there exist 0≤σ_k≤\eps_k→ 0 as k→∞, such that asymptotically almost surely the first k-regular subgraph appeared in the random graph process where one edge is added at a time has size between (1-\eps_k)|\K_k| and (1-σ_k)|\K_k|, where \K_k denotes the k-core of the graph.

Related

• On the threshold for k-regular subgraphs of random graphs
• k-regular subgraphs near the k-core threshold of a random graph
• Sprinkling with random regular graphs
• Large matchings and nearly spanning, nearly regular subgraphs of random subgraphs
• A simple solution to the k-core problem