2010/07/23 by Nicholas J. Cavenagh, Carlo Hämäläinen, Cavenagh, Nicholas +5 · 1 citation
Engineering · Computer Science · Mathematics · #graph theory and CDMA systems #Graph Labeling and Dimension Problems #Mathematics and Applications
paper · pdf · doi:10.48550/arxiv.1007.4096
A multi-latin square of order n and index k is an n× n array of multisets, each of cardinality k, such that each symbol from a fixed set of size n occurs k times in each row and k times in each column. A multi-latin square of index k is also referred to as a k-latin square. A 1-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 k-latin square of order m embeds in a k-latin square of order n, for each n≥ 2m, thus generalizing Evans' Theorem. Exploiting this result, we show that there exist non-separable k-latin squares of order n for each n≥ k+2. We also show that for each n≥ 1, there exists some finite value g(n) such that for all k≥ g(n), every k-latin square of order n is separable. We discuss the connection between k-latin squares and related combinatorial objects such as orthogonal arrays, latin parallelepipeds, semi-latin squares and k-latin trades. We also enumerate and classify k-latin squares of small orders.