Perturbation of dense graphs
Preprint
Abstract
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.
Keywords
All Related Versions
This publication has 27 references indexed in Scilit:
- On powers of tight Hamilton cycles in randomly perturbed hypergraphsRandom Structures & Algorithms, 2023
- High powers of Hamiltonian cycles in randomly augmented graphsJournal of Graph Theory, 2021
- Spanning trees in randomly perturbed graphsRandom Structures & Algorithms, 2019
- Powers of tight Hamilton cycles in randomly perturbed hypergraphsRandom Structures & Algorithms, 2019
- Powers of Hamiltonian cycles in randomly augmented graphsRandom Structures & Algorithms, 2019
- Universality for bounded degree spanning trees in randomly perturbed graphsRandom Structures & Algorithms, 2019
- Spanning structures and universality in sparse hypergraphsRandom Structures & Algorithms, 2016
- Tight Hamilton cycles in random uniform hypergraphsRandom Structures & Algorithms, 2012
- Factors in random graphsRandom Structures & Algorithms, 2008
- How many random edges make a dense graph hamiltonian?Random Structures & Algorithms, 2002