Partial Latin squares are avoidable

Nicholas J. Cavenagh nickc@maths.unsw.edu.au School of Mathematics The University of New South Wales Sydney, NSW, 2052, Australia

Lars-Daniel Öhman lars-daniel.ohman@math.umu.se Department of Mathematics and Mathematical Statistics Umeå University SE-90187 Umeå, Sweden

A square array is avoidable if for each set of n symbols there is an n × n Latin square on these symbols which differs from the array in every cell. The main result of this paper is that for m ≥ 2 any partial Latin square of order 4m − 1 is avoidable, thus concluding the proof that any partial Latin square of order at least 4 is avoidable.

MSC2000: 05B15

Keywords: Latin square, partial Latin square, avoidable array.

1 Introduction

Unless otherwise stated, all n × n arrays in this paper will have rows and columns indexed by the set {1, 2, …, n}. A Latin square of order n is an n × n array of symbols from a set S of size n such that each symbol from S occurs exactly once in each row and exactly once in each column. We say that two n × n arrays avoid each other if each pair of corresponding cells contain distinct symbols. We say that an n×n array P is avoidable if for any set S of size n there is a Latin square of order n and symbol set S such that P and S avoid each other. More specifically, we may say that an n×n array is avoidable using S, where |S| = n, if there is a Latin square with symbol set S that avoids it. A partial Latin square of order n is an array where no symbol occurs more than once in any row or column. Thus a partial Latin square is permitted to have empty cells. (Note that in this paper, we allow a partial Latin square of order n to contain more than n distinct symbols. We are thus using a more general definition of partial Latin square than is sometimes found in the literature. From the perspective of avoidability, it is convenient to make this generalization, because a Latin square on symbol set S will of course avoid any symbol not in S. Moreover, since our definition is more general, the main result in this paper certainly holds for any definition of partial Latin square in common usage.)

An isotopism of a (partial) Latin square is any reordering of the rows, reordering of the columns, relabelling of the symbol set, or any combination of these. Combinatorial properties of partial Latin squares, in particular the property of avoidability, are preserved under isotopisms. We use this fact throughout this paper.

The question of which n×n arrays are avoidable was posed by Häggkvist in 1989 [4]. Chetwynd and Rhodes [3] proved that the following partial Latin squares are avoidable.

Theorem 1.1. For m ≥ 2, all 2m × 2m and 3m × 3m partial Latin squares are avoidable.

They also showed that there is exactly one minimal non-avoidable partial Latin square of order 2 and exactly one minimal non-avoidable partial Latin square of order 3, when isotopism has been taken into account. These are given in Figure 1, and are the only non-avoidable partial Latin squares. Chetwynd and Rhodes also conjectured that any partial Latin square of order n ≥ 4 is indeed avoidable.

1 2  1 2 3 3  1 2 1

Figure 1: Non-avoidable partial Latin squares

Cavenagh [1] proved the following theorem.

Theorem 1.2. Let P be a partial Latin square of order n = 4m + 1, where m ≥ 1. Then P is avoidable.

The remaining cases of the conjecture by Chetwynd and Rhodes is then when n is congruent to 7 or 11 modulo 12. We may therefore assume that n = 4m − 1 for m ≥ 2. In this paper, we prove that the conjecture holds in this case as well.

2 Preparations

We shall need some preliminary results.

Lemma 2.1. Let P be a 3 × 3 partial Latin square. Further suppose that P has at least one empty cell. Then there is at most one set S of size 3 such P is not avoidable using S.

Proof. This can be easily gleaned from the proof of Theorem 2.2 in [3]. It is based on the fact that the 3 × 3 partial Latin square of Figure 1 is the only such unavoidable array.

When producing a Latin square L that avoids a partial Latin square P, we will say that the symbol x covers a symbol s that occurs in P if x is used in a cell in L corresponding to a cell in P where s occurs.

Lemma 2.2. Let P be an 2m × 2m partial Latin square, m ≥ 2. Suppose that the symbol x does not occur in P. Then for any set of symbols S, where |S| = 2m − 1, there is a Latin square L on symbols S ∪ {x} avoiding P in such a way that x covers either only symbols from S, or at least two distinct symbols, t_{1}, t_{2} ∉ S.

Proof. First observe that P may be avoided, using some Latin square L on symbols S ∪ {x}, by Theorem 1.1.

Suppose, for the sake of contradiction, that x covers exactly one symbol t ∉ S. Then in L we exchange symbols x and a ∈ S, and see that unless x again covers exactly one symbol not in S, we are finished. The same argument holds for any other symbol in S, so unless P contains nothing but symbols not in S we are finished. If P contains no symbols from S, we can easily find the required Latin square.

The main obstacle in the proof of the main theorem is dealt with in the following lemma. By 4-set we mean an unordered set of four elements. We define a partial transversal to be a partial Latin square in which each row has at most one symbol, each column has at most one symbol and each symbol occurs at most once.

Lemma 2.3. Let P be a 4 × 4 array on symbol set S, |S| = 4 such that:

1. no symbol is repeated in any row or column (except possibly in the last column),

2. the last column is not completely filled with one single symbol,

3. the first three columns of P contain either (A) at most three distinct symbols from S or (B) each symbol from S exactly once.

Then P is avoidable by a Latin square L on symbol set S.

Proof. Let S = {w, x, y, z}. We shall construct a Latin square L which avoids P, where L is based on the set of symbols S and P satisfies the conditions of the above claim. Relabelling the symbols of P if necessary, we set the final column of L to have symbols w, x, y and z in rows 1, 2, 3 and 4, respectively, assuming that the final column of P is avoided. (Note that this is possible because the last column of P 1 is not completely filled with exactly one symbol.) We will show that it is always possible to complete the first three columns of L so that P is avoided.

Our aim in the following is, where possible, to complete L so that x and w form a 2 × 2 subsquare in rows 1 and 2 and another 2 × 2 subsquare in rows 3 and 4. Potential obstructions to this process are the existence of x, w, z and y in rows 1, 2, 3 and 4 of P (respectively), as well as partial transversals on x and w (or y and z) within rows 1 and 2 or within rows 3 and 4. (Recall that a transversal is the only unavoidable partial Latin square of order 2.) Where enough obstructions make our goal impossible, we show an alternative way to complete L. Case A: In this case we assume that Case A of Condition (3) holds. That is, we find at most three symbols from {w, x, y, z} in the first three columns of P. Without loss of generality, assume that symbol z does not occur in the first three columns of P. We write (r, c, s) ∈ P if symbol s occurs in the cell that is the intersection of row r and column c. Now, there is at least one column c ≠ 4 such that (1, c, x) ∉ P and (2, c, w) ∉ P. We aim to place symbols x and w in cells (1, c) and (2, c) of L, respectively. However if (4, c, y) ∈ P it is then impossible to complete column c of L so that it avoids column c of P. If this is true for a unique choice of c, then, up to a relabelling of the first three columns, we can specify the following cells of P, where the last column denotes symbols in L, separated by a double line. (Since symbols w, x, y and z in rows 1, 2, 3 and 4 of P, respectively, will always be avoided by L, we can ignore any such occurrences. We thus may think of the final column in these diagrams as denoting a prohibited symbol for each row of P.)

\begin{aligned}x & & & w \\ & w & & x \\ & & & y \\ & & y & z \end{aligned}

(Throughout we ignore the symbols in the final column of P, as these are already avoided.) We label this partial Latin square P′ and deal with it later.

Otherwise we can complete column c of L, avoiding column c of P. Next, since z does not occur within P, we can fill the remaining cells in rows 1 and 2 of L with symbols y and z, avoiding the corresponding cells of P. We then have four remaining cells in rows 3 and 4 of L to fill with symbols w and x. However the symbols w and x may form a partial transversal within these four cells in P. There is at most one such partial transversal within rows 3 and 4 of P, so we are done if there are two choices for c.

It follows that we can make L avoid P unless possibly when P = P′ or P = P′′, where P′′ (up to relabelling of the first three columns) is equal to

\begin{aligned}x & & w \\ & w & x \\ w & & y \\ & x & z \end{aligned} .

However P′ is avoided by at least one of the following choices for L.

\begin{matrix}z & x & y & w \\ w & y & z & x \\ x & z & w & y \\ y & w & x & z \end{matrix} or \begin{matrix}y & x & z & w \\ w & z & y & x \\ z & w & x & y \\ x & y & w & z \end{matrix}

Also, P′′ is avoided by at least one of the following.

\begin{matrix}z & x & y & w \\ w & y & z & x \\ x & z & w & y \\ y & w & x & z \end{matrix} or \begin{matrix}y & z & x & w \\ w & y & z & x \\ z & x & w & y \\ x & w & y & z \end{matrix}

Case B: Here P satisfies Case B of Condition (3) of the claim; that is, each of w, x, y and z occurs exactly once in P. Here we can identify two rows of P, which altogether contain at most 2 symbols. Without loss of generality, let these rows be 1 and 2. Case B1: Suppose first that there are distinct columns c, c′ ≠ 4 such that (1, c, x) ∈ P and (2, c′, w) ∈ P. Let c′′ ∈ {1, 2, 3} \ {c, c′}. Case B1(a): Here (4, c′′, y) ∈ P but (3, c′′, z) ∉ P. Then we have P′ ⊂ P, where P′ is as above. Since z occurs once in P and all other cells of P are empty, P in this case avoids at least one of the following:

\begin{matrix}c & c′ & c′′ \\ z & x & y & w \\ w & y & z & x \\ x & z & w & y \\ y & w & x & z \end{matrix} or \begin{matrix}c & c′ & c′′ \\ z & y & x & w \\ w & z & y & x \\ x & w & z & y \\ y & x & w & z \end{matrix}

Case B1(b): The case where (3, c′′, z) ∈ P but (4, c′′, y) ∉ P is similar. Case B1(c): Next suppose that (3, c′′, z) and (4, c′′, y) are both in P. In this, letting c = 1, c′ = 2 and c′′ = 3, P is avoided by

\begin{matrix}c & c′ & c′′ \\ y & x & z & w \\ w & z & y & x \\ z & w & x & y \\ x & y & w & z \end{matrix} .

Case B1(d): Neither (3, c′′, z) nor (4, c′′, y) is in P. Then, since we are assuming there are at most two symbols in rows 1 and 2, letting c = 1, c′ = 2, c′′ = 3, P is avoided by

\begin{matrix}c & c′ & c′′ \\ z & y & x & w \\ y & z & w & x \\ x & w & z & y \\ w & x & y & z \end{matrix} .

Case B2: Next suppose that there is a column c ≠ 4 such that (1, c, x) ∈ P but no column c′ ∉ {4, c} such that (2, c′, w) ∈ P. Then we have two choices for a column c′′ ≠ c such that (1, c′′, x), (2, c′′, w) ∈ L, avoiding P. Since there is at most one other symbol in rows 1 and 2 of P, we can complete the first two rows of L, avoiding P in the process. If there is also a choice of c′′ for which neither (3, c′′, z) ∈ P nor (4, c′′, y) ∈ P, then it is not hard to see that L can be completed to avoid P. If there is no such choice for c′′, then P contains (with a possible reordering of the columns):

\begin{aligned}x & & & w \\ & & & x \\ & z & & y \\ & & y & z \end{aligned}

which is avoided by either

\begin{matrix}y & z & x & w \\ z & w & y & x \\ w & x & z & y \\ x & y & w & z \end{matrix} or \begin{matrix}z & y & x & w \\ w & z & y & x \\ x & w & z & y \\ y & x & w & z \end{matrix} .

Case B3: Similarly we can do the case when there is a column c ≠ 4 such that (2, c, w) ∈ P but there is no column c′ ∉ {4, c} such that (1, c′, x) ∈ P. Case B4: Henceforth we may assume that x is not in row 1 of P and that w is not in row 2 of P. We then have three choices for c ≠ 4 so that (1, c, x), (2, c, w) ∈ L, avoiding P.

We wish to fill the rest of rows 1 and 2 of L with symbols y and z. It is possible that y and z form a partial transversal in rows 1 and 2 of P. This may rule out one of our choices of c. However in this case y and z do not occur in rows 3 and 4 of P, so we can have (3, c, z), (4, c, y) ∈ L for any choice of c. Moreover a partial transversal of w and x in rows 3 and 4 of L rule out at most one more choice of c, so we can construct an L that avoids P. Otherwise symbols y and z do not form a partial transversal in rows 1 and 2 of P. In this case the only obstructions to our choice of c occur in rows 3 and 4 of P. These potential obstructions are: (1) (3, c′, z) ∈ P for some c′, (2) (4, c′′, y) ∈ P for some c′′ and (3) there is a partial transversal with x and w. Each of these scenarios rules out at most one choice for column c, so we are done unless all three obstructions occur simultaneously. In this case rows 3 and 4 of P each contain 2 symbols and rows 1 and 2 of P are empty. Here we repeat the above analysis on rows 1 and 3 rather than rows 1 and 2.

Lemma 2.4. Let P 1 and P 2 be two 4 × 4 arrays, on any symbol set, that coincide in the last (fourth) column. Suppose that in each of P 1 and P 2 no symbol is repeated in any row or column, except possibly in the last column, but that the last column is not completely filled with one single symbol.

Then there are at most R ≤ 2 · 38 = 76 4-sets of symbols that are unsuitable for producing two 4 × 4 Latin squares L1 and L2 that coincide with each other in the last column and avoid P 1 and P 2, respectively.

Proof. We will show that by excluding at most 38 distinct 4-sets {w, x, y, z} ⊂ [n] we can guarantee that for any remaining 4-set {w, x, y, z} ⊂ [n], the first three columns of P 1 contain either: (1) at most three symbols from {w, x, y, z}, or (2) each symbol from {w, x, y, z} at most once. Applying the same process to P 2, the result then follows from the previous lemma.

We first exclude the (at most) three 4-sets that are the sets of symbols used in each of the first three columns of P 1. This guarantees that each column of P 1 has a cell containing an symbol not from {w, x, y, z}, for any remaining such 4-set. Since we are hoping to make L1 avoid P 1, we label cells of P 1 that contain symbols not from {w, x, y, z} as being “empty”. Thus each column of P 1 now has at least one “empty” cell, and there are at most nine non-empty cells in the first three columns of P 1.

If these nine cells together contain at most three distinct symbols we have case (1) and are done. If the nine cells contain between four and seven distinct symbols, we can exclude the 4-sets (at most thirty-five) derived from these symbols (making a total of thirty-eight, and have case (1). If the nine cells each contain different symbols, then no matter what our choice of {w, x, y, z}, each symbol from this 4-set occurs at most once, which is case (2). Otherwise the nine cells contain seven symbols exactly once and one symbol e that occurs twice. Since 7!/(3!4!) = 35, we can exclude all 4-sets that contain the symbol e together with any three out of the seven other symbols. This implies either (1) or (2) above. So the lemma is proven.

The excluded case n = 3 in the following lemma, the statement of which which can be found in [3], and with a non-constructive proof in [2], is what makes 4m − 1 a problem for m = 3 in the main theorem.

Lemma 2.5. For any n ≠ 3 there exists an n × n Latin square on symbols 1, 2, …, n which has symbol n in each main diagonal cell and has the symbols of the last column in the same order as the symbols in the last row, namely 1, 2, …, n.

Proof. In brief, set symbol n on the main diagonal, symbol n−1 right below the diagonal, except for cell (n−1, n−3), and in cells (n−1, n) and (1, n−3). Next, fill the top left (n−2)×(n−2) subsquare by filling top-right to lowerleft diagonals with single symbols, such that the diagonal containing cell (i, i) is filled with symbol i, for 1 ≤ i ≤ n − 3. Then we will be free to use symbol i in cells (i, n) and (i, n). A closer inspection shows that row n − 1 and column n − 1 can also be completed. An example, where n = 7 follows below. It should be clear why this construction fails for n = 3, and for n ≤ 2, there clearly exists a Latin square with the required property.

7  6 6 7  1 6 7 1 6 7 1  6 7 7 6 6 7 → 7 4 2 5 6 3 1 6 7 5 3 1 4 2 2 6 7 1 4 5 3 5 3 6 7 2 1 4 3 1 4 6 7 2 5 4 5 1 2 3 7 6 1 2 3 4 5 6 7

3 The main theorem

Theorem 3.1. For n ≥ 4, any n × n partial Latin square P is avoidable.

Proof. By Theorem 1.1 and Theorem 1.2 we may assume that n = 4m − 1 for m ≥ 2. Cases m = 2 and m = 3 are handled separately in later sections. We therefore also assume that m ≥ 4.

If P is completable it is also avoidable, which can easily be seen by simply applying a permutation of the symbols without fixed points. We may therefore assume that there is an empty cell, and by permuting rows and columns we may assume that the cell (4m − 1, 4m − 1) is empty. We also assume, without loss of generality, that symbol 4m does not occur in P.

Let P′ be a 4m × 4m partial Latin square with empty last row and column, coinciding with P in the first 4m − 1 rows and columns. We shall produce a Latin square L′ on symbol set [4m] such that L′ avoids P′. Moreover, for each i ∈ [4m], we will ensure that the following conditions hold:

1. symbol 4m is on the main diagonal of L′ and

2. there exists a symbol e_{i} such that (i, 4m, e_{i}), (4m, i, e_{i}) ∈ L′ but (i, i, e_{i}) ∉ P′.

If such a Latin square L′ exists, then we create a Latin square L by deleting the last row and column of L′ and replacing symbol 4m with e_{i} in each cell (i, i). Such a latin square L will clearly avoid P.

Since m ≠ 3, by Lemma 2.5 there exists a Latin square Q on symbol set [m] such that symbol m appears only on the main diagonal, and the symbols in the last row and column appear in the same order: 1, 2, …, m. Let S = {S_{i} | 1 ≤ i ≤ m}, be a partition of [4m] into m pairwise disjoint

a b c d e f g h

Figure 2: The configuration in P (m, m)

4-sets. We will construct L by replacing each element (i, j, k) ∈ Q with a 4 × 4 Latin square (denoted by L(i, j)) on symbol set S_{k}.

Let P (i, j) be the 4×4 subarray of P′ that occupies the same set of cells as L(i, j). In order to ensure that each L(i, j) avoids the corresponding P (i, j), not all possible partitions S will be suitable. We exclude a certain number of partitions, showing ultimately that at least one partition is suitable when m ≥ 4.

Our first specification is that symbol 4m ∈ S_{m}. The number of such partitions S is equal to (4m − 1)!/((4!)^{m−1}3!). Next, for any (i, j) such that i ≠ j and i, j < m, there will be no unsuitable 4-set, because any 4 × 4 partial Latin square is avoidable using any symbol set, by Theorem 1.1.

Now consider L(m, m). The structure to be avoided will look like the array in Figure 2, where some of the symbols may be equal.

Let P (m, m)^{∗} be the partial Latin square of order 3 formed by removing the final row and column of P (m, m). We first attempt to form a Latin square L(m, m)^{∗} of order 3 on symbol set S_{m} which avoids P (m, m)^{∗}. From Lemma 2.1, there is at most one set T for which this is not possible. We specify S_{m} ≠ T ∪ \{m\}, thereby ruling out at most \frac{(4m−4)!}{(4!)^{m−1}} partitions.

Thus such a Latin square L(m, m)^{∗} exists. Next, permute the rows and columns of P′ (and the corresponding rows and columns of L(m, m)^{∗}) so that the main diagonal of L(m, m)^{∗} is a transversal. Finally, construct L(m, m) by replacing each symbol on the main diagonal of L(m, m)^{∗} with 4m, “pushing” the old symbols to the final row and column of L(m, m). Such a Latin square clearly avoids P (m, m), as well as satisfying Conditions 1 and 2 above.

Finally we must construct L(i, i), L(i, m) and L(m, i) for each i < m. First, fix i. Construct a Latin square L(i, i) on symbol set S_{m} that avoids P (i, i). Next, rearrange the row and columns of P′ (and the corresponding rows and columns of L(i, i)) so that the symbol 4m occurs on the main diagonal of L(i, i). By Lemma 2.2 (with x = 4m, P = P (i, i) and L = L(i, i)), we may also assume that among the symbols in P (i, i) that L(i, i) avoids on its main diagonal, there are either at least two distinct symbols, or only symbols used in L(i, i).

We then wish to construct L(i, m) and L(m, i) that respectively avoid P (i, m) and P (m, i) and satisfy Condition 2 above. To do this, let P (i, m)^{∗} and P (m, i)^{∗} be the arrays (possibly not partial Latin squares) formed by “pushing” the elements on the main diagonal of P (i, i) to the final row of P (m, i) and the final column of P (i, m). From above, the final row of P (m, i)^{∗} and the final column of P (i, m)^{∗} each contain either 0 or at least two distinct symbols from S_{i}.

Therefore, by Lemma 2.4, ruling out at most R ≤ 76 choices for S_{i}, there exist Latin squares L(m, i) and L(i, m) which avoid P (m, i)^{∗} and P (i, m)^{∗}, respectively. (Note that we consider the transposes of L(m, i) and P (m, i)^{∗} when applying Lemma 2.4.) Moreover, the symbols in the last row of L(m, i) correspond to the symbols in the last column of L(m, i), and these symbols in turn avoid the main diagonal of P (i, i), thus satisfying Condition 2.

By disallowing these R choices for each S_{i}, we rule out at most \frac{R(m−1)(4m−5)!}{(4!)^{m−2}3!} partitions of the symbol set. Thus, the number N of suitable partitions of the symbol set into 4-sets satisfies

\begin{aligned}N & ≥ & \frac{(4m−1)!}{(4!)^{m−1}3!} − \frac{(4m−1)!}{(4!)^{m−1}} − \frac{R(m−1)(4m−5)!}{(4!)^{m−2}3!} \\ & = & \frac{(4m−4)!}{(4!)^{m−1}} [\frac{(4m−1)(4m−2)(4m−3)−6−6R}{6}] . \end{aligned}

Using exclusion/inclusion, these calculations could be improved upon, but this simple calculation will suffice for our purposes. In order for this to be strictly greater than 0, we need 0 < (4m−1)(4m−2)(4m−3)−6−6R which, for R ≤ 76, at least holds for any m ≥ 4, and the theorem is proved.

4 The case n = 7

When proving Lemma 2.4, we excluded a larger number of 4-sets than we had a mandate for when m = 2, so we need to handle this case separately.

Theorem 4.1. Any 7 × 7 partial Latin square is avoidable.

Proof. Let P be a partial Latin square of order 7, on the symbols a, b, …, g. We will begin by partitioning L into four parts, P 1 through P 4. We set P 1 to be the top left 3 × 3 square, P 2 the top right 3 × 4 partial Latin rectangle (three rows, four columns), P 3 the lower left 4 × 3 partial Latin rectangle and P 4 the lower right 4×4 partial Latin square. We will find configurations Q1 to Q4 avoiding these parts that fit together to form a Latin square Q that avoids P.

Choose a symbol a occurring a maximal number of times and permute rows and columns so that P 2 and P 3 contain no a, but P 1 contain either all a:s (if there are three or less of them) or three a:s (if there are four or more of them). Choose a triple of symbols {b, c, d} ∌ a. We can use this triple to form a 3 × 3 Latin square Q1 that avoids P 1, by Lemma 2.1.

Next we introduce a dummy symbol x that does not occur anywhere. We use symbols {b, c, d, x} to create a 4×4 Latin square Q4′ that avoids P 4, which is possible by Theorem 1.1. We now wish to exchange the x:s for the quadruple {a, e, f, g}, each used exactly once. The only possible problem we may run into is if the four x:s should cover exactly one of these symbols four times. By Lemma 2.2 we can avoid this situation. Hence we can produce an array Q4 that avoids P 4 and that looks like a 4 × 4 Latin square on symbols {x, b, c, d}, with the modification that the x has been exchanged for a transversal on symbols a, e, f and g.

It remains to produce a Q2 that avoids P 2 and a Q3 that avoids P 3, but these two procedures are practically identical, and independent, so we shall only construct Q2. We will use symbols a, e, f and g, taking care not to run into conflict with the occurrences of these symbols that are already present in Q4. To do this, we reformulate the problem slightly: Avoid a 4 × 4 partial Latin square L4 (with its first three rows given by P 2), with the extra requirement that the last row in the avoiding Latin square, Q2′, is prescribed. The prescribed last row models the restrictions inherited from the cells where x was used in Q4, and the successful production of Q2′ follows from Lemma 2.3, since the symbol a does not occur in P 2. Q2 is simply Q2′, with the last row removed. The arrays Q1 to Q4 fit together as a Latin square, that avoids P.

5 The case n = 11

The case m = 1 of Theorem 3.1 cannot be salvaged, as there is an example of a 3 × 3 partial Latin square that is not avoidable. When m = 3, however, Lemma 2.5 also fails, and this is the case n = 4m − 1 = 11. We therefore cannot augment an 11 × 11 partial Latin square P with an extra empty row and column, partition the resulting structure P′ into 4 × 4 subsquares and follow the scheme of Theorem 3.1. Instead, we shall partition P into four 6 × 6 subarrays and follow the same scheme as Theorem 4.1. We shall need an additional lemma, mirroring Lemma 2.3.

Lemma 5.1. Let P be a 6×6 partial Latin square on the symbols 2, 3, …, 6. Let L_{0} be a 6 × 6 array with symbols 1, 2, …, 6 in its last column in that order, and suppose that L_{0} does not coincide with P in any cell. Then L_{0} can be completed to a 6 × 6 Latin square L that avoids P.

Proof. We will partition the symbol set into two suitable 3-sets, S_{1} (containing symbol 1) and S_{2}. Let R_{1} (R_{2}) be the set of rows containing symbols from S_{1} (S_{2}) in the final column of L_{0}. We partition P into four 3 × 3 subarrays P_{1} (the intersection of rows R_{1} with columns 1, 2 and 3), P_{2} (the intersection of rows R_{1} with columns 4, 5 and 6), P_{3} (the intersection of rows R_{2} with columns 4, 5 and 6) and P_{4}, (the remaining cells). we will then use S_{2} to avoid P_{1} and P_{4}, while S_{1} is used to avoid P_{2} and P_{3}.

Note that since P already avoids the final column of L_{0}, we can henceforth ignore the final column of P. We first observe that, by Lemma 2.1, S_{1} can always be used to avoid P_{3}, since symbol 1 ∈ S_{1} does not occur at all in P.

We next observe that using S_{2} = {4, 5, 6} to avoid P_{1} might pose a problem, if P_{1} contains the one non-avoidable 3 × 3 partial Latin square on symbols S_{2}. If this is the case, we may assume that column 1 contains symbols 4, 5, 6 in rows 1, 2 and 3. We permute the columns of P to bring columns 1 and 2 into columns 4 and 5. Then P_{1} will contain at most 4 occurrences of 4, 5 and 6, and will thus be avoidable. In this case P_{2} will be avoidable, for it will contain at most one occurrence of any of 2 or 3, and finally, P_{4} will be avoidable, for there will be at most one of symbols 4, 5 and 6 occurring at most once there. P_{3} stays avoidable, as observed above.

We may thus assume that P_{1} and P_{3} are avoidable, and concentrate on P_{2} and P_{4}. The approach will be a guided case analysis. The possible (minimal) obstructions fall under one of two types, as shown below, where {x, y, z} = S_{1} or S_{2}.

y  x z y z  x z y y z

We will assume that columns 4 and 5 of P are maximal, that is, we will assume it is impossible to add a symbol to any empty cell in these columns of P without repeating a symbol within a row or column (ignoring columns 1, 2, 3 and 6). This is a legitimate assumption as every case will be the subset of some maximal situation. We may thus assume that there is a row other than row 1 containing at least 2 symbols in columns 4 and 5, and without loss of generality we may assume that row 6 contains symbols 2 in column 4 and symbol 3 in column 5.

We ask now if 123, 456 (omitting curly brackets) is a suitable partition of the symbols. The possible obstructions are situated either in P_{2} or P_{4}, and up to isotopism they are one of a. b. or c. below. Similarly to the proof of Lemma 2.3, we can specify the following cells of P in columns {4, 5}, where column 6, separated by a double line, shows symbols in L. (Since any symbol e in column 6 of L avoids the corresponding symbol in P, we can ignore any occurrences of e within the same row of P. We thus may think of the final column in these diagrams as denoting a prohibited symbol for each row of P.)

a. 3  1 2 2 3 b. 5 4 4 5 2 3 6 c. 6 4 4  5 2 3 6

We treat case a. first. Is 124,356 a suitable partition? Yes, unless we have one of the following:

a.i. 2 3 6  5 2 3 6 a.ii. 5 2 3 5 2 3 6

In case a.i. 125,346 is a suitable partition unless (3, 4, 4) ∈ P. Then 134,256 is a suitable partition unless (2, 5, 5) ∈ P. Then 135,246 is a suitable partition unless (4, 5, 6) ∈ P, in which case 136,245 is a suitable partition.

In case a.ii. 125,346 is a suitable partition unless (4, 4, 6) ∈ P. Then 135,246 is a suitable partition unless (2, 5, 4) ∈ P. Then 134,256 is a suitable partition unless (5, 5, 6) ∈ P, in which case 136,245 is a suitable partition.

In case b. we ask if 146,235 is a suitable partition. The answer is yes, unless we have one of the following configurations.

b.i. 5  2 2 3 4 5 b.ii. 2 5  3 3 4 5 b.iii. 6 2 4 3 2 3 5

In case b.i. 135,246 is a suitable partition. In case b.ii. 156,234 is a suitable partition unless (2, 4, 4) ∈ P and (3, 5, 2) ∈ P. Then 125,346 is a suitable partition unless (4, 4, 6) ∈ P, in which case 256,134 is a suitable partition. In case b.iii. 156,234 is a suitable partition unless (3, 4, 4) ∈ P. Then 146,235 is a suitable partition unless (4, 4, 6) ∈ P, in which case 134,256.

In case c. we ask if 156,234 is a suitable partition. The answer is yes, unless we have one of the following configurations.

c.i. 2 2 3 3 6 4 c.ii. 3  2 4 3 6 4 c.iii. 4 2 3 3 6 4

In case c.i. 126,345 is a suitable partition unless (2, 4, 6) ∈ P, in which case 146,235 is a suitable partition. In case c.ii. 124,356 is a suitable partition, unless (3, 4, 5) ∈ P, in which case 125,346 is a suitable partition. In case c.iii. 124,356 is a suitable partition unless (3, 4, 5) ∈ P, in which case 126,345 is a suitable partition.

We can thus find a suitable partition of the symbol set, and this concludes the proof.

Theorem 5.2. Any 11 × 11 partial Latin square P is avoidable.

Proof. Let P be a partial Latin square of order 11 on the symbols 1, …, 11. We will begin by partitioning L into four parts, P 1 through P 4. We set P 1 to be the top left 5 × 5 square, P 2 the top right 5 × 6 Latin rectangle (five rows, six columns), P 3 the lower left 6 × 5 Latin rectangle and P 4 the lower right 6 × 6 partial Latin square. We will find configurations Q1 to Q4 avoiding these parts, that fit together to form a Latin square Q that avoids P.

Choose a symbol, 1, in P and permute rows and columns of P so that 1 does not occur in P 2 and P 3.

Choose a 5-set of symbols, 7, …, 11. We can use this 5-set to form a 5 × 5 Latin square Q1 that avoids P 1, (see [1]). Next we introduce a dummy symbol x that does not occur anywhere. We use symbols x, 7, …, 11 to create a 6 × 6 Latin square Q4′ that avoids P 4, which is possible by Theorem 1.1. We now wish to exchange the x:s for the 6-set 1, …, 6, each used exactly once. The only possible problem we may run into is if the six x:s should cover exactly one of these symbols six times. By Lemma 2.2 it is possible to avoid this. Hence we can produce an array Q4 that avoids P 4 and looks like a 6 × 6 Latin square on symbols x, 7, …, 11, with the modification that the x has been exchanged for a transversal on symbols 1, …, 6.

It remains to produce a Q2 that avoids P 2 and a Q3 that avoids P 3, but these two procedures are practically identical (under transpose), and independent, so we shall only construct Q2. We will use symbols 1, …, 6, taking care not to run into conflict with the occurrences of these symbols that are already present in Q4. To do this, we reformulate the problem slightly: Avoid a 6 × 6 partial Latin square L6 (with its first five rows given by P 2), with the extra requirement that the last row in the avoiding Latin square, Q2′, is prescribed. The prescribed last row models the restrictions inherited from the cells where x was used in Q4, and the successful production of Q2′ follows from the proof of Lemma 5.1, since the symbol 1 does not occur in P 2. Q2 is simply Q2′, with the last row removed.

The arrays Q1 to Q4 fit together as a Latin square that avoids P.

References

[1] N. J. Cavenagh, Avoidable partial Latin squares of order 4m + 1, Ars Comb. (to appear).

[2] A.G. Chetwynd and S.J. Rhodes, Chessboard squares, Discrete Math. 141 (1995) 47–59.

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

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