Rainbow Matchings and Hamilton Cycles in Random Graphs

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 HP(κ) 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 = Kn 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 = Kn log n where K is sufficiently large then w.h.p. there is a rainbow colored Hamilton cycle in G (n) n,m. Here G (n) n,m denotes a random edge coloring of Gn,m with n colors. When n is odd, our proof requires m = ω(n log n) for there to be a rainbow Hamilton cycle.