论文标题
稀疏图的随机扰动
Random perturbation of sparse graphs
论文作者
论文摘要
在随机扰动图的模型中，我们考虑了确定图$ \ MATHCAL {G}_α$的结合，最低度$αn$和二项式随机图$ \ Mathbb {g}（n，p）$。该模型是由Bohman，Frieze和Martin介绍的，为Hamilton循环，他们的结果弥合了Dirac定理与Posá和Koršunov在$ \ Mathbb {g}（n，p）$中的阈值之间的差距。在此注释中，我们将此结果扩展到$ \ Mathcal {g}_α\ cup \ mathbb {g}（n，p）$中，到具有$α= o（1）$的稀疏图。更准确地说，对于任何$ \ varepsilon> 0 $和$α\ colon \ mathbb {n} \ mapsto（0,1）$，我们显示A.A.S. $ \ mathcal {g}_α\ cup \ mathbb {g}（n，β/n）$是hamiltonian，其中$β= - （6 + \ varepsilon）\ log（α）$。如果$α> 0 $是固定常数，则可以给上述Bohman，Frieze和Martin的结果，如果$α= O（1/n）$，则随机部分$ \ Mathbb {g}（n，p）$足以容纳汉密尔顿周期。我们还讨论了该模型中有界度树和其他跨越结构的嵌入，这导致了几乎跨越嵌入到$ \ mathbb {g}（n，p）$中的有趣问题。
In the model of randomly perturbed graphs we consider the union of a deterministic graph $\mathcal{G}_α$ with minimum degree $α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 Posá and Koršunov on the threshold in $\mathbb{G}(n,p)$. In this note we extend this result in $\mathcal{G}_α\cup \mathbb{G}(n,p)$ to sparser graphs with $α=o(1)$. More precisely, for any $\varepsilon>0$ and $α\colon \mathbb{N} \mapsto (0,1)$ we show that a.a.s. $\mathcal{G}_α\cup \mathbb{G}(n,β/n)$ is Hamiltonian, where $β= -(6 + \varepsilon) \log(α)$. If $α>0$ is a fixed constant this gives the aforementioned result by Bohman, Frieze, and Martin and if $α=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)$.
