论文标题
随机图中的彩虹搭配和汉密尔顿周期的狄拉克型问题
Dirac-type Problem of Rainbow matchings and Hamilton cycles in Random Graphs
论文作者
论文摘要
给定图形$ g_1，\ dots，g_ {n} $在同一顶点套装$ [n] $上，彩虹汉密尔顿周期是$ [n] $的汉密尔顿周期，因此每个$ g_c $都完全贡献一个优势。我们证明，如果$ g_1，\ dots，g_ {n} $是同一顶点套装$ g（n，p）$的独立样本$ [n] $，那么对于每个$ \ varepsilon> 0 $，WHP，whp，每个跨度spanning spanning subgraphs $ h_c \ h_c \ subseteq g_c g_c $ a， $Δ（H_C）\ GEQ（\ frac {1} {2}+\ Varepsilon）NP $，承认彩虹汉密尔顿周期。在同一顶点套装$ [n] $的$ n/2 $图形的家族中，彩虹完美匹配也证明了类似的结果。
Given a family of graphs $G_1,\dots,G_{n}$ on the same vertex set $[n]$, a rainbow Hamilton cycle is a Hamilton cycle on $[n]$ such that each $G_c$ contributes exactly one edge. We prove that if $G_1,\dots,G_{n}$ are independent samples of $G(n,p)$ on the same vertex set $[n]$, then for each $\varepsilon>0$, whp, every collection of spanning subgraphs $H_c\subseteq G_c$, with $δ(H_c)\geq(\frac{1}{2}+\varepsilon)np$, admits a rainbow Hamilton cycle. A similar result is proved for rainbow perfect matchings in a family of $n/2$ graphs on the same vertex set $[n]$.
