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

Cavenagh, N., Hamalainen, C., Lefevre, J., & Stones, D. (2011). Multi-latin squares. Discrete Mathematics, 311(13), 1164 - 1171. https://doi.org/10.1016/j.disc.2010.06.026
Cavenagh, Nicholas ; Hamalainen, Carlo ; Lefevre, James ; Stones, Douglas. / Multi-latin squares. In: Discrete Mathematics. 2011 ; Vol. 311, No. 13. pp. 1164 - 1171.
@article{e248f70f5a704cffa8e0f11fc2371247,
title = "Multi-latin squares",
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",
author = "Nicholas Cavenagh and Carlo Hamalainen and James Lefevre and Douglas Stones",
year = "2011",
doi = "10.1016/j.disc.2010.06.026",
language = "English",
volume = "311",
pages = "1164 -- 1171",
journal = "Discrete Mathematics",
issn = "0012-365X",
publisher = "Elsevier",
number = "13",

}

Cavenagh, N, Hamalainen, C, Lefevre, J & Stones, D 2011, 'Multi-latin squares', Discrete Mathematics, vol. 311, no. 13, pp. 1164 - 1171. https://doi.org/10.1016/j.disc.2010.06.026

Multi-latin squares. / Cavenagh, Nicholas; Hamalainen, Carlo; Lefevre, James; Stones, Douglas.

In: Discrete Mathematics, Vol. 311, No. 13, 2011, p. 1164 - 1171.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - Multi-latin squares

AU - Cavenagh, Nicholas

AU - Hamalainen, Carlo

AU - Lefevre, James

AU - Stones, Douglas

PY - 2011

Y1 - 2011

N2 - 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

AB - 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

UR - http://arxiv.org/abs/1007.4096

U2 - 10.1016/j.disc.2010.06.026

DO - 10.1016/j.disc.2010.06.026

M3 - Article

VL - 311

SP - 1164

EP - 1171

JO - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 13

ER -

Cavenagh N, Hamalainen C, Lefevre J, Stones D. Multi-latin squares. Discrete Mathematics. 2011;311(13):1164 - 1171. https://doi.org/10.1016/j.disc.2010.06.026