论文标题
随机几何图中的彩虹汉密尔顿周期
Rainbow Hamilton Cycles in Random Geometric Graphs
论文作者
论文摘要
令$ x_1，x_2，\ ldots，x_n $独立和均匀地从单位$ d $ d $ - 二维数据集$ [0,1]^d $中随机选择。令$ r $给予，让$ \ cal x = \ {x_1，x_2，\ ldots，x_n \} $。随机几何图$ g = g _ {\ cal x，r} $具有顶点set $ \ cal x $和一个边缘$ x_ix_j $，每当$ \ | x_i-x_j \ | \ | \ | \ leq r $时。我们表明，如果$ g $的每个边缘都与$ n+o（n）$颜色的一种独立于颜色，而$ r $具有最小的价值，以至于$ g $至少具有至少两个，则$ g $包含一个彩虹汉密尔顿周期。
Let $X_1,X_2,\ldots,X_n$ be chosen independently and uniformly at random from the unit $d$-dimensional cube $[0,1]^d$. Let $r$ be given and let $\cal X=\{X_1,X_2,\ldots,X_n\}$. The random geometric graph $G=G_{\cal X,r}$ has vertex set $\cal X$ and an edge $X_iX_j$ whenever $\|X_i-X_j\|\leq r$. We show that if each edge of $G$ is colored independently from one of $n+o(n)$ colors and $r$ has the smallest value such that $G$ has minimum degree at least two, then $G$ contains a rainbow Hamilton cycle a.a.s.
