Random perturbation of sparse graphs

Max Hahn-Klimroth¹ ; Giulia Maesaka² ; Yannick Mogge³ ; Samuel Mohr⁴ ; Olaf Parczyk⁵

¹Goethe University
²Universität Hamburg
³Hamburg University of Technology
⁴Ilmenau University of Technology
⁵London School of Economics and Political Science

The electronic journal of combinatorics, Tome 28 (2021) no. 2

Résumé

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ó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)$.

Détail

DOI : 10.37236/9510

Classification : 05C42, 05C35, 05C80
Mots-clés : randomly perturbed graphs, binomial random graph