Random perturbation of sparse graphs (Q2030748)

Summary: 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 \textit{T. Bohman} et al. [Random Struct. Algorithms 22, No. 1, 33--42 (2003; Zbl 1013.05044)] and for Hamilton cycles their result bridges the gap between Dirac's theorem and the results by \textit{L. Posa} [Discrete Math. 14, 359--364 (1976; Zbl 0322.05127)] and \textit{A. D. Korsunov} [Sov. Math., Dokl. 17, 760--764 (1976; Zbl 0353.05039); translation from Dokl. Akad. Nauk SSSR 228, 529--532 (1976)] 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 et al. 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)\).