Latin Squares in Practice and in Theory II
Feature Column Archive
3. Mutually Orthogonal Latin Squares (MOLS)
After the ``Euler spoiler'' examples of Bose, Parker and Shrikhande, pairs of orthogonal latin squares were known in every size except 2 and 6. For some sizes more was known. For example, if n is a prime, then one can construct n-1 mutually orthogonal latin squares.
Four MOLS of size 5. In the first, each row is shifted one spot to the left with respect to the row above it; in the second, each is shifted two spots to the left, etc. This pattern, using the n-1 possible slopes, gives n-1 MOLS for any prime size n. |
What happens with other sizes? Let N(n) be the number of MOLS that exist of size n. It is known that
- N(n) is at most n-1;
- for primes (see above) and powers of primes, this upper bound can be attained.
Other numbers require special methods. The results are very incomplete, and the problem is currently a hot one in combinatorics. Here is a table from a recent paper by Charles Colbourn and Jeff Dinitz, reproduced with the authors' permission. They tabulate the best known lower bound on N(n), for n from 0 to 199.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 0 1 2 3 4 1 6 7 8 2 10 5 12 3 4 15 16 3 18 20 4 5 3 22 6 24 4 26 5 28 4 30 31 5 4 5 6 36 4 5 40 7 40 5 42 5 6 4 46 7 48 6 5 5 52 5 6 7 7 5 58 60 4 60 4 6 63 7 5 66 5 6 6 70 7 72 5 5 6 6 6 78 80 9 80 8 82 6 6 6 6 7 88 6 7 6 6 6 6 7 96 6 8 100 8 100 6 102 7 7 6 106 6 108 6 6 13 112 6 7 6 8 6 6 120 7 120 6 6 6 124 6 126 127 7 6 130 6 7 6 7 7 136 6 138 140 6 7 6 10 10 7 6 7 6 148 6 150 7 8 8 7 6 156 7 6 160 9 7 6 162 6 7 6 166 7 168 6 8 6 172 6 6 14 9 6 178 180 6 180 6 6 7 9 6 10 6 8 6 190 7 192 6 7 6 196 6 198 |
The current state of the art in mutually orthogonal latin squares. This table gives, for n from 0 to 199, the best known lower bound for the number N(n) of MOLS of size n. Note that for n prime or a power of a prime, the lower bound is the maximum, n-1. Numbers in red are brand new or only a few years old. For more information, consult the CRC Handbook of Combinatorial Designs. |