The square of a Hamilton cycle in randomly perturbed graphs
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2022
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866912486343573504 |
|---|---|
| author | Böttcher, Julia Parczyk, Olaf Sgueglia, Amedeo Skokan, Jozef |
| author_facet | Böttcher, Julia Parczyk, Olaf Sgueglia, Amedeo Skokan, Jozef |
| contents | We investigate the appearance of the square of a Hamilton cycle in the model of randomly perturbed graphs, which is, for a given $α\in (0,1)$, the union of any $n$-vertex graph with minimum degree $αn$ and the binomial random graph $G(n,p)$. This is known when $α> 1/2$, and we determine the exact perturbed threshold probability in all the remaining cases, i.e., for each $α\le 1/2$. We demonstrate that, as $α$ ranges over the interval $(0,1)$, the threshold performs a countably infinite number of `jumps'. Our result has implications on the perturbed threshold for $2$-universality, where we also fully address all open cases. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2202_05215 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | The square of a Hamilton cycle in randomly perturbed graphs Böttcher, Julia Parczyk, Olaf Sgueglia, Amedeo Skokan, Jozef Combinatorics We investigate the appearance of the square of a Hamilton cycle in the model of randomly perturbed graphs, which is, for a given $α\in (0,1)$, the union of any $n$-vertex graph with minimum degree $αn$ and the binomial random graph $G(n,p)$. This is known when $α> 1/2$, and we determine the exact perturbed threshold probability in all the remaining cases, i.e., for each $α\le 1/2$. We demonstrate that, as $α$ ranges over the interval $(0,1)$, the threshold performs a countably infinite number of `jumps'. Our result has implications on the perturbed threshold for $2$-universality, where we also fully address all open cases. |
| title | The square of a Hamilton cycle in randomly perturbed graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2202.05215 |