Rainbow Hamilton cycles in uniform hypergraphs (Q426813)

Summary: Let \(K_n^{(k)}\) be the complete \(k\)-uniform hypergraph, \(k\geq3\), and let \(\ell\) be an integer such that \(1\leq \ell\leq k-1\) and \(k-\ell\) divides \(n\). An \(\ell\)-overlapping Hamilton cycle in \(K_n^{(k)}\) is a spanning subhypergraph \(C\) of \(K_n^{(k)}\) with \(n/(k-\ell)\) 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 \(C\) intersects in precisely \(\ell\) vertices. We show that, for some constant \(c=c(k,\ell)\) and sufficiently large \(n\), for every coloring (partition) of the edges of \(K_n^{(k)}\) which uses arbitrarily many colors but no color appears more than \(cn^{k-\ell}\) times, there exists a rainbow \(\ell\)-overlapping Hamilton cycle \(C\), that is every edge of \(C\) receives a different color. We also prove that, for some constant \(c'=c'(k,\ell)\) and sufficiently large \(n\), for every coloring of the edges of \(K_n^{(k)}\) in which the maximum degree of the subhypergraph induced by any single color is bounded by \(c'n^{k-\ell}\), there exists a properly colored \(\ell\)-overlapping Hamilton cycle \(C\), that is every two adjacent edges receive different colors. For \(\ell=1\), both results are (trivially) best possible up to the constants. It is an open question if our results are also optimal for \(2\leq\ell\leq k-1\).The proofs rely on a version of the Lovász Local Lemma and incorporate some ideas from Albert, Frieze, and Reed.