Enumerating extensions of mutually orthogonal Latin squares
- PDF / 366,946 Bytes
- 20 Pages / 439.37 x 666.142 pts Page_size
- 65 Downloads / 192 Views
Enumerating extensions of mutually orthogonal Latin squares Simona Boyadzhiyska1 · Shagnik Das1 · Tibor Szabó1 Received: 8 October 2019 / Revised: 8 March 2020 / Accepted: 3 June 2020 © The Author(s) 2020
Abstract Two n × 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 generalise to the broader class of gerechte designs, which include Sudoku squares. Keywords Latin squares · Orthogonal mates · Gerechte designs Mathematics Subject Classification 05B15
Communicated by L. Teirlinck. 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.
B
Shagnik Das [email protected] Simona Boyadzhiyska [email protected] Tibor Szabó [email protected]
1
Institut für Mathematik, Freie Universität Berlin, 14195 Berlin, Germany
123
S. Boyadzhiyska et al.
1 Introduction Latin squares have a long and storied history in combinatorics, sharing connections to several other areas of mathematics and enjoying applications in statistics and experimental design. In particular, orthogonal Latin squares are equivalent to many other classical structures in design theory, and their study dates back to Euler. In this paper we shall answer questions concerning the enumeration of orthogonal Latin squares, but we first present some of the relevant background.
1.1 Background and related work We begin by recalling the definition of a Latin square, more in an effort to present our notation than in belief that you, the reader, do not know what a Latin square is. Definition 1 A Latin square of order n is an n × n matrix with entries in [n] such that each x ∈ [n] appears exactly once in every row and in every column. It is not difficult to see that Latin squares exist for all n; indeed, a rich class of constructions are given by the Cayley tables of groups. We refer the reader to [40] for more definitions, results and proofs related to Latin squares, noting only that the number of Latin squares is log-asymptotically given by n n 2 L(n) = (1 + o(1)) 2 . (1) e Ryser [38] showed that the lower bound follows from Van der Waerden’s conje
Data Loading...
