pith. sign in

arxiv: 1303.5139 · v2 · pith:SMAGDRJGnew · submitted 2013-03-21 · 🧮 math.CO

The first k-regular subgraph is large

classification 🧮 math.CO
keywords firstgraphk-regularlargesigmasubgraphaddedalmost
0
0 comments X
read the original abstract

We prove that for sufficiently large k, there exist $0\le\sigma_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-\sigma_k)|\K_k|$, where $\K_k$ denotes the $k$-core of the graph.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.