Gespeichert in:
| Hauptverfasser: | , , , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | https://arxiv.org/abs/2508.18042 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866914004142653440 |
|---|---|
| author | Han, Jie Im, Seonghyuk Wang, Bin Zhang, Junxue |
| author_facet | Han, Jie Im, Seonghyuk Wang, Bin Zhang, Junxue |
| contents | In the past two decades, various properties of randomly perturbed/augmented (hyper)graphs have been intensively studied, since the model was introduced by Bohman, Frieze and Martin in 2003. The model usually considers a deterministic graph $G$ with minimum degree condition, perturbed/augmented by a binomial random graph $G(n,p)$ on the same vertex set. In this paper, we show that for many problems of finding spanning subgraphs, one can indeed relax the minimum degree condition to a density condition. This includes the embedding problem for $F$-factors when $F$ is not a forest, graphs with bounded maximum degree, $r$-th power of $k$-uniform tight Hamilton cycles for $r,k\ge 2$, and $k$-uniform Hamilton $\ell$-cycles for $\ell\in[2,k-1]$. These results strengthen the results of Balogh, Treglown, and Wagner, of Böttcher, Montgomery, Parczyk, and Person, and of Chang, Han and Thoma. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_18042 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Perturbation of dense graphs Han, Jie Im, Seonghyuk Wang, Bin Zhang, Junxue Combinatorics In the past two decades, various properties of randomly perturbed/augmented (hyper)graphs have been intensively studied, since the model was introduced by Bohman, Frieze and Martin in 2003. The model usually considers a deterministic graph $G$ with minimum degree condition, perturbed/augmented by a binomial random graph $G(n,p)$ on the same vertex set. In this paper, we show that for many problems of finding spanning subgraphs, one can indeed relax the minimum degree condition to a density condition. This includes the embedding problem for $F$-factors when $F$ is not a forest, graphs with bounded maximum degree, $r$-th power of $k$-uniform tight Hamilton cycles for $r,k\ge 2$, and $k$-uniform Hamilton $\ell$-cycles for $\ell\in[2,k-1]$. These results strengthen the results of Balogh, Treglown, and Wagner, of Böttcher, Montgomery, Parczyk, and Person, and of Chang, Han and Thoma. |
| title | Perturbation of dense graphs |
| topic | Combinatorics |
| url | https://arxiv.org/abs/2508.18042 |