Sharp thresholds for higher powers of Hamilton cycles in random graphs
Fuente:
arXiv
Salvato in:
| Autori principali: | , , , |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866916622791344128 |
|---|---|
| author | Makai, Tamás Pasch, Matija Petrova, Kalina Schiller, Leon |
| author_facet | Makai, Tamás Pasch, Matija Petrova, Kalina Schiller, Leon |
| contents | For $k \geq 4$, we establish that $p = (e/n)^{1/k}$ is a sharp threshold for the existence of the $k$-th power $H$ of a Hamilton cycle in the binomial random graph model. Our proof builds upon an approach by Riordan based on the second moment method, which previously established a weak threshold for $H$. This method expresses the second moment bound through contributions of subgraphs of $H$, with two key quantities: the number of copies of each subgraph in $H$ and the subgraphs' densities. We control these two quantities more precisely by carefully restructuring Riordan's proof and treating sparse and dense subgraphs of $H$ separately. This allows us to determine the exact constant in the threshold. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_14515 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Sharp thresholds for higher powers of Hamilton cycles in random graphs Makai, Tamás Pasch, Matija Petrova, Kalina Schiller, Leon Combinatorics 05C80, 05D40 For $k \geq 4$, we establish that $p = (e/n)^{1/k}$ is a sharp threshold for the existence of the $k$-th power $H$ of a Hamilton cycle in the binomial random graph model. Our proof builds upon an approach by Riordan based on the second moment method, which previously established a weak threshold for $H$. This method expresses the second moment bound through contributions of subgraphs of $H$, with two key quantities: the number of copies of each subgraph in $H$ and the subgraphs' densities. We control these two quantities more precisely by carefully restructuring Riordan's proof and treating sparse and dense subgraphs of $H$ separately. This allows us to determine the exact constant in the threshold. |
| title | Sharp thresholds for higher powers of Hamilton cycles in random graphs |
| topic | Combinatorics 05C80, 05D40 |
| url | https://arxiv.org/abs/2502.14515 |