Multi-latin squares

A multi-latin square of order nn and index kk is an n×nn×n array of multisets, each of cardinality kk, such that each symbol from a fixed set of size nn occurs kk times in each row and kk times in each column. A multi-latin square of index kk is also referred to as a kk-latin square. A 11-latin square is equivalent to a latin square, so a multi-latin square can be thought of as a generalization of a latin square.In this note we show that any partially filled-in kk-latin square of order mm embeds in a kk-latin square of order nn, for each n≥2mn≥2m, thus generalizing Evans’ Theorem. Exploiting this result, we show that there exist non-separable kk-latin squares of order nn for each n≥k+2n≥k+2. We also show that for each n≥1n≥1, there exists some finite value g(n)g(n) such that for all k≥g(n)k≥g(n), every kk-latin square of order nn is separable.We discuss the connection between kk-latin squares and related combinatorial objects such as orthogonal arrays, latin parallelepipeds, semi-latin squares and kk-latin trades. We also enumerate and classify kk-latin squares of small orders.