Enumerating extensions of mutually orthogonal Latin squares

DOI10.1007/S10623-020-00771-6MaRDI QIDQ2004974zbMATH OpenOpenAlexFDO

Authors Simona Boyadzhiyska, Shagnik Das, Tibor Szabó

Publication date 7 October 2020

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1910.02753

zbMATH Keywords

gerechte designsLatin squaresorthogonal mates

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Orthogonal arrays, Latin squares, Room squares (05B15)

Abstract: Two $nimesn$ 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.

Review text

In this paper, the authors establish that the logarithm of the number of ways a \(k\)-MOLS of order \(n\) can be extended to a \((k+1)\)-MOLS, with \(0\leq k\leq n-2\), is at most \[n^2\int_0^1\log(1+(n-1)t^{k+2})dt.\] They generalize indeed this bound for the ways to extend a nearly orthogonal array by one column and hence, for the more general class of gerechte designs. Based on the asymptotic behavior of such bounds, the authors establish some upper bounds for the total number of \(k\)-MOLS of order \(n\), when \(k\) grows with \(n\). Some illustrative constructions are described and some related open problems concerning orthogonal mates of Latin squares, affine and projective planes, and mutually orthogonal Sudoku squares are enumerated.

Recommendations

• scientific article; zbMATH DE number 874490
• On the maximality of a set of mutually orthogonal sudoku Latin squares
• Embedding partial Latin squares in Latin squares with many mutually orthogonal mates
• Enumeration of MOLS of small order
• scientific article; zbMATH DE number 894713

Cites work

• A course in combinatorics.
• A note on orthogonal Latin squares
• Additive triples of bijections, or the toroidal semiqueens problem
• An entropy proof of Bregman's theorem
• An upper bound on the number of Steiner triple systems
• Coloured and directed designs
• Commutative semifields and symplectic spreads.
• Concerning the number of mutually orthogonal latin squares
• Counting Steiner triple systems
• Enumeration of MOLS of small order
• scientific article; zbMATH DE number 5178940 (Why is no real title available?)
• scientific article; zbMATH DE number 3968597 (Why is no real title available?)
• scientific article; zbMATH DE number 107482 (Why is no real title available?)
• scientific article; zbMATH DE number 3458807 (Why is no real title available?)
• scientific article; zbMATH DE number 5879559 (Why is no real title available?)
• scientific article; zbMATH DE number 3340244 (Why is no real title available?)
• scientific article; zbMATH DE number 4183425 (Why is no real title available?)
• Latin squares with no transversals
• Multidimensional permanents and an upper bound on the number of transversals in Latin squares
• Mutually orthogonal families of linear sudoku solutions
• On a problem of Erdős and Lovász: Random lines in a projective plane
• On defining sets for projective planes
• On Embedding and Enumeration of Orthogonal Latin Squares
• On the Maximal Number of Pairwise Orthogonal Latin Squares of a Given Order
• On the maximum number of Latin transversals
• On the number of Sudoku squares
• On the number of transversal designs
• Orthogonal arrays. Theory and applications
• Orthogonal combings of linear sudoku solutions
• Proof of the van der Waerden conjecture regarding the permanent of a doubly stochastic matrix
• Small latin squares, quasigroups, and loops
• Sudoku, Gerechte Designs, Resolutions, Affine Space, Spreads, Reguli, and Hamming Codes
• Symplectic semifield planes and ℤ₄–linear codes
• The existence of Latin squares without orthogonal mates
• The number of mates of Latin squares of sizes 7 and 8
• The solution of van der Waerden's problem for permanents

Cited in

(10)

• Enumeration of semi-Latin squares
• Embedding partial Latin squares in Latin squares with many mutually orthogonal mates
• On the maximality of a set of mutually orthogonal sudoku Latin squares
• Difference covering arrays and pseudo-orthogonal Latin squares
• scientific article; zbMATH DE number 6007683 (Why is no real title available?)
• scientific article; zbMATH DE number 927062 (Why is no real title available?)
• The enumeration of cyclic mutually nearly orthogonal Latin squares
• Quadratic permutations, complete mappings and mutually orthogonal latin squares
• Enumeration formulas for latin and frequency squares
• Mutually orthogonal binary frequency squares

This page was built for publication: Enumerating extensions of mutually orthogonal Latin squares

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2004974)