Enumerating extensions of mutually orthogonal Latin squares

Simona Boyadzhiyska; Shagnik Das; Tibor Szabó

doi:10.1007/s10623-020-00771-6

Enumerating extensions of mutually orthogonal Latin squares

Simona Boyadzhiyska, Shagnik Das^*, Tibor Szabó

^*Corresponding author for this work

Mathematics

Research output: Contribution to journal › Article › peer-review

1 Citation (Scopus)

Abstract

Two n× n Latin squares L₁, L₂ are said to be orthogonal if, for every ordered pair (x, y) of symbols, there are coordinates (i, j) such that L₁(i, j) = x and L₂(i, j) = y. A k-MOLS is a sequence of k pairwise-orthogonal Latin squares, and the existence and enumeration of these objects has attracted a great deal of attention. Recent work of Keevash and Luria provides, for all fixed k, log-asymptotically tight bounds on the number of k-MOLS. To study the situation when k grows with n, we bound the number of ways a k-MOLS can be extended to a (k+ 1) -MOLS. These bounds are again tight for constant k, and allow us to deduce upper bounds on the total number of k-MOLS for all k. These bounds are close to tight even for k linear in n, and readily generalise to the broader class of gerechte designs, which include Sudoku squares.

Original language	English
Pages (from-to)	2187-2206
Number of pages	20
Journal	Designs, Codes, and Cryptography
Volume	88
Issue number	10
DOIs	https://doi.org/10.1007/s10623-020-00771-6
Publication status	Published - 1 Oct 2020

Bibliographical note

Funding Information:
S. Boyadzhiyska was supported by the Deutsche Forschungsgemeinschaft (DFG) Graduiertenkolleg “Facets of Complexity” (GRK 2434). S. Das was supported in part by the Deutsche Forschungsgemeinschaft (DFG) Project 415310276. S. Das and T. Szabó were supported in part by the German-Israeli Foundation for Scientific Research and Development (GIF) Grant G-1347-304.6/2016.

Publisher Copyright:
© 2020, The Author(s).

Keywords

Gerechte designs
Latin squares
Orthogonal mates

ASJC Scopus subject areas

Computer Science Applications
Applied Mathematics

Access to Document

10.1007/s10623-020-00771-6

Cite this

@article{a2ea9e9746204f3a9abe8a7235b18c7e,

title = "Enumerating extensions of mutually orthogonal Latin squares",

abstract = "Two n× n Latin squares L1, L2 are said to be orthogonal if, for every ordered pair (x, y) of symbols, there are coordinates (i, j) such that L1(i, j) = x and L2(i, j) = y. A k-MOLS is a sequence of k pairwise-orthogonal Latin squares, and the existence and enumeration of these objects has attracted a great deal of attention. Recent work of Keevash and Luria provides, for all fixed k, log-asymptotically tight bounds on the number of k-MOLS. To study the situation when k grows with n, we bound the number of ways a k-MOLS can be extended to a (k+ 1) -MOLS. These bounds are again tight for constant k, and allow us to deduce upper bounds on the total number of k-MOLS for all k. These bounds are close to tight even for k linear in n, and readily generalise to the broader class of gerechte designs, which include Sudoku squares.",

keywords = "Gerechte designs, Latin squares, Orthogonal mates",

author = "Simona Boyadzhiyska and Shagnik Das and Tibor Szab{\'o}",

note = "Funding Information: S. Boyadzhiyska was supported by the Deutsche Forschungsgemeinschaft (DFG) Graduiertenkolleg “Facets of Complexity” (GRK 2434). S. Das was supported in part by the Deutsche Forschungsgemeinschaft (DFG) Project 415310276. S. Das and T. Szab{\'o} were supported in part by the German-Israeli Foundation for Scientific Research and Development (GIF) Grant G-1347-304.6/2016. Publisher Copyright: {\textcopyright} 2020, The Author(s).",

year = "2020",

month = oct,

day = "1",

doi = "10.1007/s10623-020-00771-6",

language = "English",

volume = "88",

pages = "2187--2206",

journal = "Designs, Codes, and Cryptography",

issn = "0925-1022",

publisher = "Springer",

number = "10",

}

TY - JOUR

T1 - Enumerating extensions of mutually orthogonal Latin squares

AU - Boyadzhiyska, Simona

AU - Das, Shagnik

AU - Szabó, Tibor

N1 - Funding Information: S. Boyadzhiyska was supported by the Deutsche Forschungsgemeinschaft (DFG) Graduiertenkolleg “Facets of Complexity” (GRK 2434). S. Das was supported in part by the Deutsche Forschungsgemeinschaft (DFG) Project 415310276. S. Das and T. Szabó were supported in part by the German-Israeli Foundation for Scientific Research and Development (GIF) Grant G-1347-304.6/2016. Publisher Copyright: © 2020, The Author(s).

PY - 2020/10/1

Y1 - 2020/10/1

N2 - Two n× n Latin squares L1, L2 are said to be orthogonal if, for every ordered pair (x, y) of symbols, there are coordinates (i, j) such that L1(i, j) = x and L2(i, j) = y. A k-MOLS is a sequence of k pairwise-orthogonal Latin squares, and the existence and enumeration of these objects has attracted a great deal of attention. Recent work of Keevash and Luria provides, for all fixed k, log-asymptotically tight bounds on the number of k-MOLS. To study the situation when k grows with n, we bound the number of ways a k-MOLS can be extended to a (k+ 1) -MOLS. These bounds are again tight for constant k, and allow us to deduce upper bounds on the total number of k-MOLS for all k. These bounds are close to tight even for k linear in n, and readily generalise to the broader class of gerechte designs, which include Sudoku squares.

AB - Two n× n Latin squares L1, L2 are said to be orthogonal if, for every ordered pair (x, y) of symbols, there are coordinates (i, j) such that L1(i, j) = x and L2(i, j) = y. A k-MOLS is a sequence of k pairwise-orthogonal Latin squares, and the existence and enumeration of these objects has attracted a great deal of attention. Recent work of Keevash and Luria provides, for all fixed k, log-asymptotically tight bounds on the number of k-MOLS. To study the situation when k grows with n, we bound the number of ways a k-MOLS can be extended to a (k+ 1) -MOLS. These bounds are again tight for constant k, and allow us to deduce upper bounds on the total number of k-MOLS for all k. These bounds are close to tight even for k linear in n, and readily generalise to the broader class of gerechte designs, which include Sudoku squares.

KW - Gerechte designs

KW - Latin squares

KW - Orthogonal mates

UR - http://www.scopus.com/inward/record.url?scp=85087419220&partnerID=8YFLogxK

U2 - 10.1007/s10623-020-00771-6

DO - 10.1007/s10623-020-00771-6

M3 - Article

AN - SCOPUS:85087419220

SN - 0925-1022

VL - 88

SP - 2187

EP - 2206

JO - Designs, Codes, and Cryptography

JF - Designs, Codes, and Cryptography

IS - 10

ER -

Enumerating extensions of mutually orthogonal Latin squares

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this