A328873 Maximal size of a set of pairwise mutually orthogonal diagonal Latin squares of order n.

1, 0, 0, 2, 2, 1, 4, 6, 6

Offset

1,4

Comments

From Andrew Howroyd, Nov 08 2019: (Start)

A diagonal Latin square of order n is an n X n array with every integer from 0 to n-1 in every row, every column, and both main diagonals.

Of course if even one example exists, then a(n) >= 1.

A274806 gives the number of diagonal Latin squares and A274806(6) is nonzero. This suggests that although it is not possible to have a pair of orthogonal diagonal Latin squares, a(6) should be 1 here. (End)

a(1) = 1 because there is only one (trivial) diagonal Latin square of order 1. It is orthogonal to itself, so if we allow the consideration of multiple copies of the same diagonal Latin square, we get a(1) = infinity instead.

From Eduard I. Vatutin, Mar 27 2021: (Start)

a(n) <= A287695(n) + 1.

a(p) >= A123565(p) = p-3 for all odd prime p due to existance of clique from cyclic MODLS of order p with at least A123565(p) items. It seems that for some orders p clique from cyclic MODLS can be extended by adding none cyclic DLS that are orthogonal to all cyclic DLS. (End)

a(9) >= 6. - Eduard I. Vatutin, Oct 29 2019

a(n) <= A001438(n). - Max Alekseyev, Nov 08 2019

a(10) >= 2; a(11) >= 8; a(12) >= 2; a(13) >= 10; a(14) >= 2; a(15) >= 4. - Natalia Makarova, Sep 03 2020

Conjecture: a(9) = 6. - Natalia Makarova, Dec 24 2020

a(16) >= 14, a(17) >= 14, a(18) >= 2, a(19) >= 16, a(20) >= 2. - Natalia Makarova, Jan 08 2021

a(12) >= 4. - Natalia Makarova, May 30 2021

Links

Table of n, a(n) for n=1..9.

R. J. R. Abel, Charles J. Colbourn, and Jeffrey H. Dinitz,  Mutually Orthogonal Latin Squares (MOLS) [Note the first author, Julian Abel, has the initials R. J. R. A. - N. J. A. Sloane, Nov 05 2020]

B. Du, New Bounds For Pairwise Orthogonal Diagonal Latin Squares, Australasian Journal of Combinatorics 7 (1993), pp.87-99.

Natalia Makarova, MODLS of order 15

Natalia Makarova, Complete MOLS systems

Natalia Makarova, Orthogonal Diagonal Latin squares

Natalia Makarova, Mutually Orthogonal Diagonal Latin squares (MODLS) for orders 9 - 20

Natalia Makarova, MOLS and MODLS of order 12

E. I. Vatutin, Discussion about properties of diagonal Latin squares (in Russian), Oct 29 2019.

Eduard I. Vatutin, On the falsity of Makarova's proof that a(9) = 6 (in Russian).

Eduard I. Vatutin, About the cliques from orthogonal diagonal Latin squares of order 9, brute force based proof that a(9) = 6 (in Russian).

E. I. Vatutin, M. O. Manzuk, V. S. Titov, S. E. Kochemazov, A. D. Belyshev, N. N. Nikitina, Orthogonality-based classification of diagonal latin squares of orders 1-8, High-performance computing systems and technologies. Vol. 3. No. 1. 2019. pp. 94-100. (in Russian).

E. I. Vatutin, N. N. Nikitina, M. O. Manzuk, O. S. Zaikin, A. D. Belyshev, Cliques properties from diagonal Latin squares of small order, Intellectual and Information Systems (Intellect - 2019). Tula, 2019. pp. 17-23. (in Russian).

Eduard I. Vatutin, About the A328873(N)-1 <= A287695(N) inequality between the maximum cardinality of clique and the maximum number of orthogonal normalized mates for one diagonal Latin square (in Russian).

Eduard I. Vatutin, Proving list (best known examples).

Wikipedia, Clique problem.

Index entries for sequences related to Latin squares and rectangles.

Example

Orthogonal pair of Diagonal Latin squares of order 18:
   1  5 15 16 17 18  2 14  4 13  3  7 12 10  8  6 11  9
   8  2  6 15 16 17 18  1  5 14  4 13 11  9  7 12 10  3
  14  9  3  7 15 16 17  2  6  1  5 12 10  8 13 11  4 18
  13  1 10  4  8 15 16  3  7  2  6 11  9 14 12  5 18 17
  12 14  2 11  5  9 15  4  8  3  7 10  1 13  6 18 17 16
  11 13  1  3 12  6 10  5  9  4  8  2 14  7 18 17 16 15
   3 12 14  2  4 13  7  6 10  5  9  1  8 18 17 16 15 11
   9 10 11 12 13 14  1 15 16 17 18  8  7  6  5  4  3  2
   6  7  8  9 10 11 12 18 17 16 15  5  4  3  2  1 14 13
   5  6  7  8  9 10 11 16 15 18 17  4  3  2  1 14 13 12
   7  8  9 10 11 12 13 17 18 15 16  6  5  4  3  2  1 14
   4 15 16 17 18  1  8 13  3 12  2 14  6 11  9  7  5 10
  15 16 17 18 14  7  9 12  2 11  1  3 13  5 10  8  6  4
  16 17 18 13  6  8  3 11  1 10 14 15  2 12  4  9  7  5
  17 18 12  5  7  2  4 10 14  9 13 16 15  1 11  3  8  6
  18 11  4  6  1  3  5  9 13  8 12 17 16 15 14 10  2  7
  10  3  5 14  2  4  6  8 12  7 11 18 17 16 15 13  9  1
   2  4 13  1  3  5 14  7 11  6 10  9 18 17 16 15 12  8
and
   1  8 14 13 12 11  3  9  6  5  7  4 15 16 17 18 10  2
   5  2  9  1 14 13 12 10  7  6  8 15 16 17 18 11  3  4
  15  6  3 10  2  1 14 11  8  7  9 16 17 18 12  4  5 13
  16 15  7  4 11  3  2 12  9  8 10 17 18 13  5  6 14  1
  17 16 15  8  5 12  4 13 10  9 11 18 14  6  7  1  2  3
  18 17 16 15  9  6 13 14 11 10 12  1  7  8  2  3  4  5
   2 18 17 16 15 10  7  1 12 11 13  8  9  3  4  5  6 14
  14  1  2  3  4  5  6 15 16 17 18 13 12 11 10  9  8  7
   4  5  6  7  8  9 10 17 18 15 16  3  2  1 14 13 12 11
  13 14  1  2  3  4  5 18 17 16 15 12 11 10  9  8  7  6
   3  4  5  6  7  8  9 16 15 18 17  2  1 14 13 12 11 10
   7 13 12 11 10  2  1  8  5  4  6 14  3 15 16 17 18  9
  12 11 10  9  1 14  8  7  4  3  5  6 13  2 15 16 17 18
  10  9  8 14 13  7 18  6  3  2  4 11  5 12  1 15 16 17
   8  7 13 12  6 18 17  5  2  1  3  9 10  4 11 14 15 16
   6 12 11  5 18 17 16  4  1 14  2  7  8  9  3 10 13 15
  11 10  4 18 17 16 15  3 14 13  1  5  6  7  8  2  9 12
   9  3 18 17 16 15 11  2 13 12 14 10  4  5  6  7  1  8
so a(18) >= 2.

Crossrefs

Cf. A001438, A274806, A287695.

Sequence in context: A193597 A191490 A061598 * A071946 A053495 A096747

Adjacent sequences: A328870 A328871 A328872 * A328874 A328875 A328876

Keyword

nonn,more,hard

Author

Eduard I. Vatutin, Oct 29 2019

Extensions

a(6) corrected by Max Alekseyev and Andrew Howroyd, Nov 08 2019

a(9) added by Eduard I. Vatutin, Feb 02 2021

Status

approved