Page 54 - Ellingham, Mark, Mariusz Meszka, Primož Moravec, Enes Pasalic, 2014. 2014 PhD Summer School in Discrete Mathematics. Koper: University of Primorska Press. Famnit Lectures, 3.
P. 54
2.2 Latin squares
Construction of a pair of orthogonal latin squares of odd order n.
Let S = n . Then L 1(i , j ) = (i + j ) modn and L 2(i , j ) = (i − j ) modn .
Let N (n) denote the largest number of latin squares in a set of MOLS(n).
Remark. For every n, 1 ≤ N (n) ≤ n − 1.
Theorem 8. If q = p k is a prime power, then N (q ) = q − 1.
Construction of a set of n-1 MOLS of order q = p k , where p is a prime.
Let q be a finite field of order q . Let α0, α1, . . . , αq−1 be elements of q , where α0 is a
zero element. For each nonzero element αr (r = 0) in q , define a latin square L r (i , j ) =
αr × αi + αj .
Determining the value of N (n) remains one of the most foremost problems in com-
binatorics. For instance, it is known that N (3) ≥ 3 for all n = 2, 3, 6 and possibly 10.
Definition 5. A partial latin square of order n is an n × n array in which some cells are
empty and some are filled with elements of S, such that each element of S appears in
every row and every column at most once.
Theorem 9. Any partial latin square of order n which has at most n − 1 cells occupied can
be completed to a latin square.
Deciding whether a partial latin square can be completed is an NP-complete prob-
lem, even if there are no more than 3 unfilled cells in any row or column.
Definition 6. A latin rectangle of size m × n (m ≤ n) is an m × n array with entries from a
set S of cardinality n such that every row is a permutation of S and every column contains
no repetition.
Theorem 10. If L is an m × n latin rectangle, then one can append n − m further rows to
L so that the resulting array in a latin square.
Definition 7. Let a , b and n be positive integers with a × b = n. Let an n × n array be
partitioned into disjoint a × b regions. An (a ,b )-Sudoku latin square is a latin square on
the set {1, 2, . . . , n} where each region contains all of the symbols. An (a ,b )-Sudoku criti-
cal set of size k is a partial latin square P with k nonempty cells that may be completed
in exactly one way to an (a ,b )-Sudoku latin square, but removal of any of the filled cells
from P destroys the uniqueness of a completion.
Example 11. A (3, 3)-Sudoku critical set of size 17:
1
4
2
547
83
19
342
51
86
Construction of a pair of orthogonal latin squares of odd order n.
Let S = n . Then L 1(i , j ) = (i + j ) modn and L 2(i , j ) = (i − j ) modn .
Let N (n) denote the largest number of latin squares in a set of MOLS(n).
Remark. For every n, 1 ≤ N (n) ≤ n − 1.
Theorem 8. If q = p k is a prime power, then N (q ) = q − 1.
Construction of a set of n-1 MOLS of order q = p k , where p is a prime.
Let q be a finite field of order q . Let α0, α1, . . . , αq−1 be elements of q , where α0 is a
zero element. For each nonzero element αr (r = 0) in q , define a latin square L r (i , j ) =
αr × αi + αj .
Determining the value of N (n) remains one of the most foremost problems in com-
binatorics. For instance, it is known that N (3) ≥ 3 for all n = 2, 3, 6 and possibly 10.
Definition 5. A partial latin square of order n is an n × n array in which some cells are
empty and some are filled with elements of S, such that each element of S appears in
every row and every column at most once.
Theorem 9. Any partial latin square of order n which has at most n − 1 cells occupied can
be completed to a latin square.
Deciding whether a partial latin square can be completed is an NP-complete prob-
lem, even if there are no more than 3 unfilled cells in any row or column.
Definition 6. A latin rectangle of size m × n (m ≤ n) is an m × n array with entries from a
set S of cardinality n such that every row is a permutation of S and every column contains
no repetition.
Theorem 10. If L is an m × n latin rectangle, then one can append n − m further rows to
L so that the resulting array in a latin square.
Definition 7. Let a , b and n be positive integers with a × b = n. Let an n × n array be
partitioned into disjoint a × b regions. An (a ,b )-Sudoku latin square is a latin square on
the set {1, 2, . . . , n} where each region contains all of the symbols. An (a ,b )-Sudoku criti-
cal set of size k is a partial latin square P with k nonempty cells that may be completed
in exactly one way to an (a ,b )-Sudoku latin square, but removal of any of the filled cells
from P destroys the uniqueness of a completion.
Example 11. A (3, 3)-Sudoku critical set of size 17:
1
4
2
547
83
19
342
51
86
