On the threshold for k-regular subgraphs of random graphs
| dc.creator | Pralat, Pawel | |
| dc.creator | Verstraete, Jacques | |
| dc.creator | Wormald, Nicholas | |
| dc.date | 2007-06-08 | |
| dc.date.accessioned | 2026-07-07T08:04:36Z | |
| dc.date.available | 2026-07-07T08:04:36Z | |
| dc.description | 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$. | |
| dc.identifier | https://arxiv.org/abs/0706.1103 | |
| dc.identifier | http://arxiv.org/abs/0706.1103 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/130024 | |
| dc.subject | Combinatorics | |
| dc.subject | Probability | |
| dc.title | On the threshold for k-regular subgraphs of random graphs | |
| dc.type | text |