Rainbow matchings and Hamilton cycles in random graphs1. Issue 3 (6th July 2015)

• Record Type: Journal Article
• Authors: Bal, Deepak; Frieze, Alan
• Is Part Of: Random structures & algorithms. Volume 48:Issue 3(2016)
• Page Start: 503
• Page End: 523
• Publication Date: 2015-07-06
• Subjects: random hypergraphs -- perfect matchings -- rainbow colorings -- latin transversal; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20594
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Let H P n, 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 H P n, m, k ( κ ) be an edge colored version, where we color each edge randomly from one of κ colors. We show that if κ = n and m = K n log n 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 = K n log n where K is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle in G n, m ( n ) . Here G n, m ( n ) denotes a random edge coloring of G n, m with n colors. When n is odd, our proof requires m = ω ( n log n ) for there to be a rainbow Hamilton cycle. © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 48, 503–523, 2016