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

arXiv2211.05477MaRDI QIDQ6416786FDOQ6416786

Authors: Asaf Ferber, Jie Han, Dingjia Mao 

Publication date: 10 November 2022

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_i$ 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_{i}subseteq{G}_i$, with $delta(H_i)geq(frac12+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]$. Our method is likely to be applicable to further problems in the rainbow setting, in particular, we illustrate how it works for finding a rainbow perfect matching in the $k$-partite $k$-uniform hypergraph setting.

This page was built for publication: Dirac-type Problem of Rainbow matchings and Hamilton cycles in Random Graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6416786)