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.

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)