@article{HMMMP20randomperturbationsparse,
title = {Random perturbation of sparse graphs},
author = {Hahn-Klimroth, Max and Maesaka, Giulia S. and Mogge, Yannick and Mohr, Samuel and Parczyk, Olaf},
archivePrefix = {arXiv},
eprint = {2004.04672},
journal = {Electronic Journal of Combinatorics},
year = {2021},
doi = {10.37236/9510},
volume={28},
number={2},
pages={P2.26},
biburl = {http://samuel-mohr.de/files/bib/13.bib},
abstract = { In the model of randomly perturbed graphs we consider the union of a deterministic graph {$\mathcal{G}_\alpha$} with minimum degree {$\alpha n$} and the binomial random graph {$\mathbb{G}(n,p)$}. This model was introduced by Bohman, Frieze, and Martin and for Hamilton cycles their result bridges the gap between Dirac's theorem and the results by P\'{o}sa and Korshunov on the threshold in {$\mathbb{G}(n,p)$}.
In this note we extend this result in {$\mathcal{G}_\alpha \cup \mathbb{G}(n,p)$} to sparser graphs with {$\alpha=o(1)$}.
More precisely, for any {$\varepsilon>0$} and {$\alpha \colon \mathbb{N} \mapsto (0,1)$} we show that a.a.s. {$\mathcal{G}_\alpha \cup \mathbb{G}(n,\beta /n)$} is Hamiltonian, where {$\beta = -(6 + \varepsilon) \log(\alpha)$}.
If {$\alpha>0$} is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if {$\alpha=O(1/n)$} the random part {$\mathbb{G}(n,p)$} is sufficient for a Hamilton cycle.
We also discuss embeddings of bounded degree trees and other spanning structures in this model, which lead to interesting questions on almost spanning embeddings into {$\mathbb{G}(n,p)$}.
},
}