Clique decompositions of multipartite graphs and completion of latin squares

Our main result essentially reduces the problem of finding an edge-decomposition of a balanced r-partite graph of large minimum degree into r-cliques to the problem of finding a fractional r-clique decomposition or an approximate one. Together with very recent results of Dukes as well as Montgomery on fractional decompositions into triangles and cliques respectively, this gives the best known bounds on the minimum degree which ensures an edge-decomposition of an r-partite graph into r-cliques (subject to trivially necessary divisibility conditions). The 3-partite case significantly improves existing bounds, the case r ≥ 4 extends a result of Chowla, Erdős and Straus on the existence of r-clique decompositions of complete r-partite graphs to non-complete r-partite graphs. The case of triangles translates into the setting of partially completed Latin squares and more generally the case of r-cliques translates into the setting of partially completed mutually orthogonal Latin squares.