Rainbow decompositions

Abstract:

A rainbow coloring of a graph is a coloring of the edges with distinct colors. We prove the following extension of Wilson’s Theorem. For every integer $k$ there exists an $n_0=n_0(k)$ so that for all $n > n_0$, if \[ n \bmod k(k-1) \in \{1,k\},\] then every properly edge-colored $K_n$ contains $\binom {n}{2}/\binom {k}{2}$ pairwise edge-disjoint rainbow copies of $K_k$. Our proof uses, as a main ingredient, a double application of the probabilistic method.