Rainbow matchings and Hamilton cycles in random graphs

Deepak Bal, Alan Frieze

Research output: Contribution to journalArticle

6 Scopus citations

Abstract

Let HPn,m,k be drawn uniformly from all m-edge, k-uniform, k-partite hypergraphs where each part of the partition is a disjoint copy of [n]. We let HPn,m,k(κ) be an edge colored version, where we color each edge randomly from one of κ colors. We show that if κ=n and m=Knlogn where K is sufficiently large then w.h.p. there is a rainbow colored perfect matching. I.e. a perfect matching in which every edge has a different color. We also show that if n is even and m=Knlogn where K is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle in Gn,m(n). Here Gn,m(n) denotes a random edge coloring of Gn,m with n colors. When n is odd, our proof requires m=ω(nlogn) for there to be a rainbow Hamilton cycle.

Original languageEnglish
Pages (from-to)503-523
Number of pages21
JournalRandom Structures and Algorithms
Volume48
Issue number3
DOIs
StatePublished - 1 May 2016

Keywords

  • Latin transversal
  • Perfect matchings
  • Rainbow colorings
  • Random hypergraphs

Fingerprint Dive into the research topics of 'Rainbow matchings and Hamilton cycles in random graphs'. Together they form a unique fingerprint.

  • Cite this