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...
Saved in:
Published in: | Discrete mathematics 2011-07, Vol.311 (13), p.1164-1171 |
---|---|
Main Authors: | , , , |
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!
|
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 |