Latin squares with prescriptions and restrictions

Lars-Daniel Öhman

Abstract. We investigate the question of when it is possible to produce an n × n Latin square that abides by two types of specifications: The prescription that a certain symbol be used in a certain cell, and the restriction that a certain symbol must not be used in a certain cell. When only one or two symbols are involved in the specifications, we solve the problem completely.

1. Introduction

An array A, for our purposes, is a rectangular arrangement of symbols, {a_{ij}}_{i,j}, with the possibility of discerning distinct symbols. Rows are indexed by i and columns by j, and if 1 ≤ i ≤ m and 1 ≤ j ≤ n we say that A is an m × n array. In what follows, we shall only consider square arrays, i.e. where m = n. When there is talk of ‘subarrays’, the object in question is the set of cells that is the intersection of a selection of rows and a selection of columns. Any subarray can thus, by suitable permutations of the rows and columns, be brought together into an r × s connected rectangle of cells, even though the original cells may be scattered around the whole initial array.

Two arrays are isotopic if one can be transformed into the other by suitable permutations of the rows, the columns and/or the symbols. In somewhat non-standard terminology, we shall say that two arrays are isomorphic if they are either isotopic, or by exchanging the role of rows and columns in one of them, they become isotopic. In geometric terms, what differs between isomorphy and isotopy is the possibility to reflect along the main diagonal. Obviously, two isotopic arrays are isomorphic, and these relations are equivalence relations. All results in this paper are up to isomorphism.

An n × n array is avoidable if for each set of n symbols there is a Latin square on these symbols which differs from the array in every cell. The question of which n × n arrays are avoidable was posed by Häggkvist in 1989 [6]. Further results of Chetwynd and Rhodes [3], Cavenagh [1] and Cavenagh and the present author [2], established that there are unavoidable partial Latin squares of orders 2 and 3, and that all partial Latin squares of order at least 4 are avoidable. An attempt at classifying all unavoidable arrays was undertaken by Markström and the present author in [7].

The question of which partial Latin squares are completable is well studied, but it seems natural to consider the possibility of there being both prescribed and forbidden symbols. To the present author’s knowledge, these are the first stumbling steps on this path of investigation. An array that defines specifications which can not be met we shall call unabiding, the opposite of which, of course, is abiding. A Latin square L abides by A if it has all the prescribed symbols where they should be, and no symbols where they shouldn’t be, according to the specifications codified in A.

A moment’s reflection gives that it is uninteresting to allow multiple prescribed symbols in any cell, for this would immediately render the array unabiding. Likewise, forbidding the use of some symbol in a cell where some other symbol has already been prescribed is superfluous, and if we should forbid the use of a symbol in a cell where we have already prescribed it, the array is trivially unabiding. It is, however, meaningful to allow multiple forbidden symbols in any given cell. This line of investigation has been pursued in [4] and [5], but we introduce here the new element of additional prescribed symbols.

2. Arrays with one distinct symbol

Any partial Latin square on one symbol is completable; the diagonal on the only symbol can trivially be completed, and by König’s colouring theorem, any partial Latin square consisting of a number of complete diagonals is completable. Characterizing the unavoidable arrays on one symbol is simply a matter of applying Hall’s theorem on distinct representatives. We quote from [7]:

Proposition 2.1. An array A on one symbol that holds an r × (n − r + 1) rectangular subarray totally filled with that single symbol is unavoidable.

Further, any unavoidable n × n array using only one symbol has, for some 1 ≤ r ≤ n, an r × (n − r + 1) rectangular subarray totally filled with that single symbol.

We shall use the letter B for the active symbol, B where it is forbidden, and b where it is prescribed. As observed above, if a b and a B occupy the same cell, the array is unabiding, and if the b:s do not form a partial Latin square, or the condition from Proposition 2.1 on the placement of the B:s is violated, again the array is unabiding.

We will also find reason to make reference to the following lemmata, likewise from [7], which state when an avoidable array with only one distinct forbidden symbol forces the use of this symbol in a specific cell.

Lemma 2.2. Let A be an n × n avoidable array on the symbol B. Suppose that any Latin square that avoids A must use the symbol b in each of the cells in the set S. Then for each cell c ∈ S, A contains, for some r, an r × (n − r + 1) rectangular subarray that covers c and is totally filled with the symbol B, except for cell c, which is empty.

Lemma 2.3. Let A be an n × n avoidable array on the symbol B. Suppose that any Latin square that avoids A must use the symbol b in at least one of the cells in the set of cells S. Then there is a nonempty subset T ⊂ S, such that A contains an r×(n−r+1) rectangular subarray that covers T and is totally filled with the symbol B, except for cells in T, which are empty.

In what follows, we will often consider only certain parts of an array, where all the action is. For instance, we know immediately that any row or column where there is a prescribed b will hold no further b:s. When attempting to complete a partial diagonal on b, we need therefore only consider what happens in the subarray obtained from A by removing any row or column containing b. The following definition is therefore useful.

Definition 2.4. We denote by A_{b} the subarray obtained from A by removing all rows and columns containing the symbol b. By A_{¬b} we denote the subarray obtained from A by removing all rows and columns not containing b.

When considering arrays with more than one kind of symbol, Lemma 2.2 is not quite enough. We therefore prove the following extension of it.

Lemma 2.5. Let k denote the number of b:s in the n × n abiding array A on symbols b and B. A forces the use of the symbol b in a cell c iff A_{b} contains, for some r, an r × ((n − k) − r + 1) subarray A_{0} ∋ c completely filled with B, except for cell c, which is empty.

Proof. We need only consider A_{b}, for no further b will be placed outside of A_{b}. Since there are k b:s in all, A_{b} is an (n − k) × (n − k) subarray, and by Lemma 2.2, we are forced to place a b in c ∈ A_{b} iff for some r there is an r × ((n − k) − r + 1) subarray A_{0} in A_{b} such that A_{b} \ {c} is filled with B:s. □

We now present the characterisation of unabiding arrays on one symbol.

Theorem 2.6. An array A using the symbol B for forbidding the use of symbol b in a cell and the symbol b for prescribing the use in a cell is abiding iff no B and b occupy a common cell, the b:s form a partial Latin square, and the subsquare A_{b} does not for any r contain an r × ((n − k) − r + 1) rectangular subarray completely filled with the symbol B, where k is the number of b:s in A.

Proof. Necessity. We must show that if any one of the conditions are violated, then A is unabiding. If a b and a B should occupy a common cell, A is obviously unabiding. Also, if the b:s do not in themselves form a partial Latin square, we have no hope of constructing a Latin square that abides by A. Further, if the (n − k) × (n − k) subsquare A_{b}, in which we must complete the partial diagonal specified by the b:s, holds a subrectangle as specified in the present proposition, then Proposition 2.1 clearly states that this can not be done, and hence A is unabiding. Sufficiency. The prescribed b:s form a partial Latin square, that does not in itself constitute a breach against any B. Rather, they form a partial diagonal T. In the array A_{b} as defined above, we can find another partial diagonal T_{0} by Proposition 2.1, since there is no ‘large’ rectangle of B:s in A_{b}. T and T_{0} together form a complete diagonal, and completing this to a full Latin square is trivial, as there are no specifications for the rest of the symbols. □

b B B B B  b b B B

Figure 1. Examples of unabiding arrays on one symbol

3. Arrays with two distinct symbols

As noted in the previous section, an array with two complete, non-intersecting diagonals on symbols b and d respectively is always completable. Unavoidable arrays with two distinct forbidden symbols were completely characterised in [7]:

Theorem 3.1. Let A be an n × n unavoidable array with two distinct symbols, b and d, that does not constitute an unavoidable array when either symbol is completely removed. Then A contains one r × (n − r + 1) array R_{b} and one (n − r + 1) × r array R_{d} as follows: R_{b} and R_{d} intersect in a single cell c which is empty, and the rest of R_{i} is filled with the symbol i for i = b, d.

If A contains subarrays as described in the theorem, then A is unavoidable, since in cell c both the symbol b and the symbol d is forced, so the theorem is in effect ‘if-and-only-if’. Note that Theorem 3.1 does not allow multiple entries in any cell. That situation seems considerably more complicated. In what follows we shall likewise restrict ourselves to arrays with no two forbidden symbols in any cell, so each cell will hold at most one specification.

Before we go for greater generality, we will investigate what happens when the symbols only appear as prescriptions and/or restrictions. We shall start with the case when the two symbols are only prescribed.

Proposition 3.2. Let A be an n × n array with symbols b and d prescribed, in disjoint sets of cells. Then A is completable iff both the b:s and d:s form partial Latin squares, and the following does not hold:

A contains a partial diagonal T of length n−1 in one of the symbols, say b, together with one or both of the following, where c is the cell that would complete T to a full diagonal:

(I). Cell c contains a d.

(II). A_{¬b} contains an (n − 1) diagonal T_{d} filled with d:s.

Proof. Necessity. If the b:s or d:s do not form partial Latin squares, we have no hope of completing A. In both case (I) and case (II), the b:s force the use of a b in cell c. In case (I), the cell is already occupied, and in case (II), the d:s in T_{d} force the use of a d in cell c. Sufficiency. Suppose first that the neither the number of b:s nor c:s is n − 1. If any of the two diagonals should already be complete, we are happy. Suppose that the number of b:s is strictly less than n − 1. Then A_{b} is at least 2 × 2, and since there is at most one d in any row or column, it can be completed. The same argument holds for d, so we are finished in this case.

Now suppose we have exactly n − 1 b:s. Since (I) does not hold, the partial diagonal on b can be completed. If the number of d:s is not exactly n − 1, we are finished, for then we can complete the diagonal on d if it is not already complete.

If the number of d:s should happen to be n − 1, and we cannot complete the diagonal they form, we see by switching names on b and d that we have either case (I) or case (II), and we are finished. □

b d b d d  b  b b  d d b d b

Figure 2. Examples of unabiding arrays on symbols b and d

Next, we treat the case where one symbol is prescribed, and the other forbidden. Note that this proposition properly contains Proposition 2.1.

Proposition 3.3. Let A be an n×n array with symbols b and D prescribed and forbidden, respectively, in disjoint sets of cells. Then A is abiding iff the b:s form a partial Latin square, and none of the following holds:

(I). For some r, the union of the set of cells containing D:s and the set of cells con-

taining b:s contains an r × (n − r + 1) subarray of A. (II). There are n − 1 b:s and for some r, the set of cells containing D:s and the set

of cells containing b:s together with the cell c = A_{b}, contains an r × (n − r + 1) subarray.

Proof. Necessity. Trivially, if the b:s do not form a partial Latin square, then A is unabiding. Further, if (I) holds, then by Proposition 2.1, we can find no place to put a full diagonal of d:s. If (II) holds, we must place a b in cell c, and subsequently, again by Proposition 2.1, we will not find place enough for a full diagonal of d:s. Sufficiency. Suppose the b:s form a partial Latin square, and that none of (I) and (II) holds. If there are exactly n b:s, they form a full diagonal, and since (I) does not hold, by Proposition 2.1, we can also find space enough for a full diagonal of d:s, and we are finished. If there are exactly n − 1 b:s, then we complete this partial diagonal to a full diagonal in the only possible way (namely filling cell c with a b), and since (II) does not hold, there is still room for a diagonal of d:s. Finally, if there are at most n − 2 b:s present in the partial diagonal T_{b}, we shall start by choosing a diagonal in which to put d:s, which is possible by Proposition 2.1, since (I) does not hold. We must still complete the partial diagonal on b, so we investigate the subarray A_{b}, which is at least 2 × 2. In A_{b}, at most one cell in each row and column now holds a d, so we can find an empty diagonal T_{0} in which to put b:s, that together with T_{b} forms a full diagonal on b, and we are finished. □

b D D D b D  b b D b D D D

Figure 3. Examples of unabiding arrays on b and D

We now investigate the case when one symbol, say D, takes both roles (prescription and restriction) and the other symbol B takes only the prescriptive role. If the number of either of these should be zero, we refer back to Theorem 2.6 or the previous propositions in this section.

Theorem 3.4. Let A be an array on symbols b, d and D, that is abiding when any one of these symbols is disregarded in its entirety. Let k be the number of d:s in A. Then A is abiding iff none of the following holds:

(I). There are (n − 1) b:s, and for some r, A_{d} contains an r × ((n − k) − r + 1) array

A_{0} ∋ c = A_{b} completely filled with D:s and b:s, except for cell c which is empty. (II). A_{d} contains, for some r, an r × ((n − k) − r + 1) subarray A_{0} completely filled with

D:s and b:s.

Proof. Necessity. If case (I) occurs, we see by Lemma 2.5 that we will have to place a d in cell c, but clearly, we would also have to place a b there. If case (II) occurs, there is not enough room for a diagonal of d:s, again by Lemma 2.5. Sufficiency. If there are exactly n b:s, they form a full diagonal, and consequently, we only have to worry about completing the diagonal on d. In doing this, we treat any b as a position where we are forbidden to place a d. Therefore, by Theorem 2.6 A is abiding if case (II) does not occur.

If there are strictly less than (n − 2) b:s, then we may always complete the diagonal on b after completing the diagonal on d, so again, we need only worry about completing the diagonal on d. By Proposition 2.6 this is possible if (II) does not occur.

Finally, if there are exactly (n − 1) b:s, it may happen that we are forced to place a d in cell c = A_{b}, creating an unresolvable conflict. By Lemma 2.5, this will happen iff case (I) occurs. Ensuring that the diagonal on d is completable, amounts to making sure that case (II) does not occur. □

b d B B d  b d b b D D

Figure 4. Examples of unabiding arrays on symbols b, d and D.

The following theorem, which concludes the characterisation of unabiding arrays on two symbols, presupposes that there are both B:s and D:s present. If either of them should be missing, we resort instead to Theorem 3.4.

Theorem 3.5. Let A be an array on symbols b, B, d and D, that is abiding when any one of these symbols is disregarded in its entirety. Let k be the number of b:s, and ℓ be the number of d:s in A, where either of these number might be zero, whereas the number of B:s and D:s are both nonzero. Then A is abiding iff the following does not hold:

For some r and s, there is in A_{b} ∩ A_{d} an empty cell c with the following properties: There exists an r × ((n − k) − r + 1) subarray A_{0} ⊂ A_{b} that covers the cell c, the rest of which is filled with B:s and d:s, and an s × ((n − ℓ) − s + 1) subarray A_{1} ⊂ A_{d} that covers the cell c, the rest of which is filled with D:s and b:s.

Proof. Necessity. If there indeed exists such a cell, we are forced to use both a b and a d there, so A is unabiding. Sufficiency. We assume that A is unabiding, and must show that there exists a cell c that fulfills the conditions stated.

We begin with attempting to place a full diagonal of b:s. No D will affect the possibility of doing this, and may therefore be disregarded. Since the number of D:s is non-zero and, by assumption, A is abiding when all D:s are disregarded, it is possible to place a diagonal of b:s.

We next try to complete the partial diagonal on d. This takes place in A_{d}. By Proposition 2.1 it is possible to complete the diagonal on d iff there for no t exists a t×((n−k)−t+1) subarray in A_{d} where we are forbidden to place a d. There are two distinct reasons for which we may be forbidden to place a d in a given cell. Either the cell holds a D, or we there is a b in it, either present already in A, or placed there by us. We draw the conclusion that for any possible diagonal T_{b} on b, there is a set of cells S ⊂ A_{d} ∩ T_{b} such that S together with the D:s in A_{d} forms an r × ((n − k) − r + 1) subarray for some r.

If we fix a diagonal on b, no two cells of S lie in the same row or column, since it is contained in a diagonal. Next, if |S ∩ A_{b}| ≥ 2 for some diagonal of b:s, we could reform the diagonal so that we did not use b:s in the empty cells of an r ×((n−k)−r +1) rectangular subarray otherwise filled with D:s. For |S| = 2 this procedure is illustrated in Figure 5. We read “X/y” as X being forbidden, and y being used in that cell. ∅ indicates an empty cell.

\begin{matrix}∅/b & … & D/∅ \\ … & & … \\ D/∅ & … & ∅/b \end{matrix}  →  \begin{matrix}∅/∅ & … & D/b \\ … & & … \\ D/b & … & ∅/∅ \end{matrix}

Figure 5. Reforming S

We see therefore that there are single cells in A_{b} ∩ A_{d}, the union of which we name M_{d}, where the symbol d must be used. By reversing the roles of b and d in the above argument, we find a set of cells M_{b}, in each of which we must use a b. We see then that M_{b}, M_{d} ⊂ A_{b} ∩ A_{d}.

We claim that if A is unabiding, then M_{b} ∩ M_{d} ≠ ∅. Then any cell c ∈ M_{b} ∩ M_{d} fulfills the conditions in the statement of the theorem.

Any diagonal on b intersects M_{d}, and vice versa. Therefore, M_{b} ∪ M_{d} forms a partial diagonal. By Lemma 2.3 there exists a non-empty set of cells T ⊂ M_{d} such that there is an r × ((n − k) − r + 1) subarray A_{T} ⊂ A_{b} where A_{T} \ T is filled with B:s and d:s.

If |T | = 1, we have that T ⊂ M_{b}. If it were the case that |T | ≥ 2, we would not be forced to use d in the cells of T, contradicting the fact that T ⊂ M_{d}. To see why this is so, we take, for example, the case |T | = 2. Figure 6 shows how the d:s claimed to be forced in the two cells of T can be moved.

\begin{matrix}B/∅ & … & ∅/d \\ … & & … \\ ∅/d & … & B/∅ \end{matrix}  →  \begin{matrix}B/d & … & ∅/∅ \\ … & & … \\ ∅/∅ & … & B/d \end{matrix}

Figure 6. Reforming T

Thus |T | = 1 and therefore T ⊂ M_{b}, so that T ⊂ M_{b} ∩ M_{d}. □

b D D D  B B d  b  d b D D  B

Figure 7. Examples of unabiding arrays on two symbols

4. Concluding remarks

A natural extension of the present results would be to consider what happens when we allow some cells to contain the entry {B, D}. This, however, seems to be considerably more complicated. As an indication of this, we present in Figure 8 two examples of unabiding arrays with entries from the set {B, D, {B, D}}, taken from [7].

B,D B D D B

B,D B,D
B,D  B D
B,D D B

Figure 8. Examples of unabiding arrays with entries from {B, D, {B, D}}

Another obvious path of investigation is allowing three or more symbols to be involved in the specifications, but again, this seems like a tough nut to crack. In Figure 9 two other unabiding arrays from [7], this time with three distinct symbols, are presented to illustrate the potentially rich flora of arrays in this category.

B D E E  B D B  B B D E B B E D D D E E

Figure 9. Examples of unabiding arrays on three symbols

References

[1] N. J. Cavenagh, Avoidable partial latin squares of order 4m + 1, Ars Combin., to appear.

[2] N. J. Cavenagh and L–D. Öhman, Partial Latin squares are avoidable, Research Report in Mathematics 2 (2006) Dept. of mathematics and mathematical statistics, Umeå University, Umeå. Submitted to Ann. Comb.

[3] A. G. Chetwynd and S. J. Rhodes, Avoiding partial Latin squares and intricacy, Discrete Math. 177 (1997) 17–32.

[4] A. G. Chetwynd & S. J. Rhodes, Avoiding multiple entry arrays, J. Graph Theory 25 (1997) 257–266.

[5] J. Cutler and L–D. Öhman, Latin squares with forbidden entries, Electron. J. Combin. 13(1) (2006) R47.

[6] R. Häggkvist, A note on Latin squares with restricted support, Discrete Math. 75 (1989) 253–254.

[7] K. Markström and L–D. Öhman, Unavoidable arrays, submitted to Electron. J. Combin.

  E-mail address: lars-daniel.ohman@math.umu.se