Dirac-type Problem of Rainbow matchings and Hamilton cycles in Random Graphs

Abstract

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 $\epsilon >0$, whp, every collection of spanning subgraphs $H_c\subseteq G_c$, with $\hat{I}´(H_c)\ge (\frac{1}{2}+\epsilon )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]$.

14 pages, new results added (Theorem 1.4, 1.5)