Rainbow Hamilton cycles in uniform hypergraphs

<p>Let K(k)n be the complete k-uniform hypergraph, k≥3, and let ℓ be an integer such that 1≤ℓ≤k−1 and k−ℓ divides n. An ℓ-overlapping Hamilton cycle in K(k)n is a spanning subhypergraph C of K(k)n with n/(k−ℓ) edges and such that for some cyclic ordering of the vertices each edge of C consists of k consecutive vertices and every pair of adjacent edges in Cintersects in precisely ℓ vertices.<br>We show that, for some constant c=c(k,ℓ) and sufficiently large n, for every coloring (partition) of the edges of K(k)n which uses arbitrarily many colors but no color appears more than cnk−ℓ times, there exists a rainbow ℓ-overlapping Hamilton cycle C, that is every edge of C receives a different color. We also prove that, for some constant c′=c′(k,ℓ) and sufficiently large n, for every coloring of the edges of K(k)n in which the maximum degree of the subhypergraph induced by any single color is bounded by c′nk−ℓ, there exists a properly colored ℓ-overlapping Hamilton cycle C, that is every two adjacent edges receive different colors. For ℓ=1, both results are (trivially) best possible up to the constants. It is an open question if our results are also optimal for 2≤ℓ≤k−1.<br>The proofs rely on a version of the Lovász Local Lemma and incorporate some ideas from Albert, Frieze, and Reed.</p>