Rainbow matchings and Hamilton cycles in random graphs

Deepak Bal, Alan Frieze

Research output: Contribution to journalArticleResearchpeer-review

6 Citations (Scopus)

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

Fingerprint

Hamilton Cycle
Random Graphs
Color
Perfect Matching
Edge Coloring
Coloring
Hypergraph
Disjoint
Odd
Partition
Denote

Keywords

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

Cite this

@article{c5fddf0ec6f24002839409282e19a749,
title = "Rainbow matchings and Hamilton cycles in random graphs",
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.",
keywords = "Latin transversal, Perfect matchings, Rainbow colorings, Random hypergraphs",
author = "Deepak Bal and Alan Frieze",
year = "2016",
month = "5",
day = "1",
doi = "10.1002/rsa.20594",
language = "English",
volume = "48",
pages = "503--523",
journal = "Random Structures and Algorithms",
issn = "1042-9832",
publisher = "John Wiley and Sons Ltd",
number = "3",

}

Rainbow matchings and Hamilton cycles in random graphs. / Bal, Deepak; Frieze, Alan.

In: Random Structures and Algorithms, Vol. 48, No. 3, 01.05.2016, p. 503-523.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Rainbow matchings and Hamilton cycles in random graphs

AU - Bal, Deepak

AU - Frieze, Alan

PY - 2016/5/1

Y1 - 2016/5/1

N2 - 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.

AB - 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.

KW - Latin transversal

KW - Perfect matchings

KW - Rainbow colorings

KW - Random hypergraphs

UR - http://www.scopus.com/inward/record.url?scp=84961212812&partnerID=8YFLogxK

U2 - 10.1002/rsa.20594

DO - 10.1002/rsa.20594

M3 - Article

VL - 48

SP - 503

EP - 523

JO - Random Structures and Algorithms

JF - Random Structures and Algorithms

SN - 1042-9832

IS - 3

ER -