Back to Search Start Over

Enumerating extensions of mutually orthogonal Latin squares

Authors :
Boyadzhiyska, Simona
Das, Shagnik
Szabó, Tibor
Publication Year :
2019

Abstract

Two $n \times n$ Latin squares $L_1, L_2$ are said to be orthogonal if, for every ordered pair $(x,y)$ of symbols, there are coordinates $(i,j)$ such that $L_1(i,j) = x$ and $L_2(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 generalize to the broader class of gerechte designs, which include Sudoku squares.<br />Comment: 18 pages

Subjects

Subjects :
Mathematics - Combinatorics
05B15

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.1910.02753
Document Type :
Working Paper