@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)$}. }, }