Rainbow matchings and Hamilton cycles in random graphs1. Issue 3 (6th July 2015) - Bal, Deepak; Frieze, Alan
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