论文标题
彩虹汉密尔顿周期随机颜色随机扰动密集图
Rainbow Hamilton cycles in randomly coloured randomly perturbed dense graphs
论文作者
论文摘要
考虑到$ n $ vertex Graph $ g $具有至少$ d> 0 $至少$ d n $的$ d n $，$ g $上的超级插图上的分配$ g \ cup \ cup \ cup \ mathbb {g}（n，p）$称为（随机）（随机）{\ sl perturbation} of $ g $ $ g $。我们考虑通过分配随机扰动的每个边缘$ g \ cup \ mathbb {g}（n，p）$ a颜色而产生的边彩图的分布，从一组大小$ r：= r（n）$中独立和均匀地选择。我们证明了这种边缘色的图形分布A.A.S.接纳彩虹汉密尔顿周期，每当随机扰动的边缘密度满足$ p：= p（n）\ geq c/n $，对于某些固定$ c> 0 $，而$ r =（1 + o（1））n $。使用的颜色数量显然是渐进的。特别是，这在这方面取决于Anastos和Frieze（2019）的最新结果。作为可能具有独立关注的中间结果，我们证明了随机边缘稀疏的伪随机图A.A.A.S.承认几乎跨越彩虹的路。
Given an $n$-vertex graph $G$ with minimum degree at least $d n$ for some fixed $d > 0$, the distribution $G \cup \mathbb{G}(n,p)$ over the supergraphs of $G$ is referred to as a (random) {\sl perturbation} of $G$. We consider the distribution of edge-coloured graphs arising from assigning each edge of the random perturbation $G \cup \mathbb{G}(n,p)$ a colour, chosen independently and uniformly at random from a set of colours of size $r := r(n)$. We prove that such edge-coloured graph distributions a.a.s. admit rainbow Hamilton cycles whenever the edge-density of the random perturbation satisfies $p := p(n) \geq C/n$, for some fixed $C > 0$, and $r = (1 + o(1))n$. The number of colours used is clearly asymptotically best possible. In particular, this improves upon a recent result of Anastos and Frieze (2019) in this regard. As an intermediate result, which may be of independent interest, we prove that randomly edge-coloured sparse pseudo-random graphs a.a.s. admit an almost spanning rainbow path.
