Loading…

Multi-latin squares

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 e...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics 2011-07, Vol.311 (13), p.1164-1171
Main Authors: Cavenagh, Nicholas, Hämäläinen, Carlo, Lefevre, James G., Stones, Douglas S.
Format: Article
Language:English
Subjects:
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 ≥ 2 m , 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.
ISSN:0012-365X
1872-681X
DOI:10.1016/j.disc.2010.06.026