Multi-latin squares

Nicholas Cavenagh, Carlo Hamalainen, James Lefevre, Douglas Stones

Research output: Contribution to journalArticleResearchpeer-review

4 Citations (Scopus)

Abstract

A multi-latin square of order n and index k is an n x 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
Original languageEnglish
Pages (from-to)1164 - 1171
Number of pages8
JournalDiscrete Mathematics
Volume311
Issue number13
DOIs
Publication statusPublished - 2011

Cite this