The first k-regular subgraph is large

We prove that for sufficiently large k, there exist $0\leσ_k\le\eps_k\to 0$ as $k\to\infty$, 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.

No reviews yet.

No comments yet.