Definition:Let L(n) be the largest value of k for which there exists a SOMA(k,n).
Definition: Let N(n) be the largest value for k for which there exists k MOLS of order n, or equivalently a Trojan SOMA(k,n).
Definition: Let M(n) be the largest value for k for which there exists a non-Trojan SOMA(k,n).
We briefly discuss upper and lower bounds for L(n).
It is obvious that L(n) is the largest defined value of N(n) and of M(n).
A lower bound for L(n) is given by Soicher in [Soi99]. In Theorem 1 of this paper, Soicher shows that a decomposable SOMA(3,n) exists, for every n ≥ 4. Hence L(n) ≥ 3, for every n ≥ 4.
Soicher has constructed an indecomposable SOMA(4,10), which is shown here. This SOMA together with known results on MOLS gives that L(n) ≥ 4, for every n ≥ 5 such that n ≠ 6, except possibly when n=18 or n=22.
We now briefly discuss upper and lower bounds for N(n).
It is known that N(n) ≤ n-1, for all n. It is also known that if n is a prime power then N(n)=n-1. We remark here that the existence of n-1 MOLS of order n is still a major unsolved problem, when n is not a prime power.
It is known that two MOLS of order n exist, except when n=2 or n=6. So we have that N(n) ≥ 2 , for all n ≥ 3 and n ≠ 6. We remark here that the existence of three MOLS of order 10 is still a major unsolved problem.
We briefly discuss upper and lower bounds for M(n).
An upper bound is given in:
R. A. Bailey, Efficient Semi-Latin squares, Statistica Sinica Vol. 2, No.2 (1992), pp. 413-437.
In Theorem 6.4 of this paper, Bailey shows that every SOMA(n-1,n) is Trojan. So M(n) ≤ n-2, when M(n) exists. A problem on the upper bound of M(n) is given by BCC problem 16.19, which can be found in the British Combinatorial Problem List given here. This problem asks whether every SOMA(n-2,n) must be Trojan. In other words, it asks whether M(n) ≤ n-3 when M(n) exists. We have answered this problem in the positive in the following paper:
John Arhin, Every SOMA(n-2,n) is Trojan, Discrete Mathematics (2008),
doi: 10.1016/j.disc.2008.09.050.
It trivial to see that every SOMA(1,n) is Trojan. We recall that one of my thesis results is that an indecomposable SOMA(2,n) exists, except when n ≤ 4. So we have a lower bound M(n) ≥ 2, for all n ≥ 5.
We briefly look at some values, or best known lower bounds, for L(n), M(n) and N(n). We remark that hyperlinks are given to explain some of these values, or bounds.
A table of some known values and lower bounds for L(n), M(n) and N(n)
We remark that the bounds L(14) ≥ 4, N(14) ≥ 3 and M(14) ≥ 4 are explained in Section 8 of Soi99.
This page is maintained by John Arhin.
Last updated: September 5th 2007.