Document Type

Article

Publication Title

Designs, Codes and Cryptography

Publication Date

2025

Keywords

Latin squares, embedding, Ore's theorem, Ryser's theorem, multi-Latin squares

Abstract

We prove a general result on completing objects similar to Latin rectangles in which the number of occurrences of each symbol is prescribed, each cell contains multiple symbols, and no cell contains repeated symbols. This generalizes several results in the literature, and leads to confirming a conjecture of Cavenagh, Hämäläinen, Lefevre, and Stones. An r × s λ-Latin rectangle L is an r × s array in which each cell contains a multiset of λ elements from the set {1, . . . , n} of symbols such that each symbol occurs at most λ times in each row and column. If r = s = n, then L is a λ-Latin square. A λ-Latin rectangle is simple if no symbol is repeated in any cell. Cavenagh et al. asked for conditions that ensure a simple λ-Latin rectangle can be extended to a simple λ-Latin square. We solve this problem in a more general setting by allowing the number of occurrences of each symbol to be prescribed. Cavenagh et al. conjectured that for each r, λ there exists some n(r, λ) such that for any n n(r, λ), every simple partial λ-Latin square of order r (each cell contains at most λ symbols) embeds in a simple λ-Latin square of order n. We confirm this conjecture.

Funding Source

This article was published Open Access thanks to a transformative agreement between Milner Library and Springer Nature.

Comments

First published in Designs, Codes and Cryptography:https://doi.org/10.1007/s10623-025-01728-3

DOI

10.1007/s10623-025-01728-3

Download

Share

COinS