Sharp thresholds for spanning regular subgraphs
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866913910857138176 |
|---|---|
| author | Zhukovskii, Maksim |
| author_facet | Zhukovskii, Maksim |
| contents | We prove that $(1+o(1))\sqrt{e/n}$ is the sharp threshold for the appearance of the square of a Hamilton cycle in $G(n,p)$, confirming the conjecture of Kahn, Narayanan, and Park. We also find the exact asymptotics of the threshold for the emergence of a spanning subgraph isomorphic to a fixed graph $F$ for a wide family of $d$-regular graphs $F$. This family includes almost all $d$-regular graphs. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_14794 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sharp thresholds for spanning regular subgraphs Zhukovskii, Maksim Combinatorics We prove that $(1+o(1))\sqrt{e/n}$ is the sharp threshold for the appearance of the square of a Hamilton cycle in $G(n,p)$, confirming the conjecture of Kahn, Narayanan, and Park. We also find the exact asymptotics of the threshold for the emergence of a spanning subgraph isomorphic to a fixed graph $F$ for a wide family of $d$-regular graphs $F$. This family includes almost all $d$-regular graphs. |
| title | Sharp thresholds for spanning regular subgraphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2502.14794 |