Rainbow matchings and Hamilton cycles in random graphs

Let H P n , m , kbe 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 inG n , m ( n ). HereG n , m ( n )denotes a random edge coloring ofG n , mwith 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