{
  "id": "2211.05477",
  "version": "v1",
  "published": "2022-11-10T10:45:16.000Z",
  "updated": "2022-11-10T10:45:16.000Z",
  "title": "Dirac-type Problem of Rainbow matchings and Hamilton cycles in Random Graphs",
  "authors": [
    "Asaf Ferber",
    "Jie Han",
    "Dingjia Mao"
  ],
  "comment": "13 pages",
  "categories": [
    "math.CO"
  ],
  "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(\\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]$. 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2022-11-10T10:45:16.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "dirac-type problem",
      "rainbow matchings",
      "random graphs",
      "rainbow hamilton cycle",
      "vertex set"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 13,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}