Unavoidable arrays

Klas Markström and Lars-Daniel Öhman

Abstract. We investigate edge list-colourings of complete bipartite graphs, where the lists are shorter than the length guaranteed by Galvin’s theorem to allow proper colourings. We phrase our results in terms of Latin squares.

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. We characterise all unavoidable square arrays with at most 2 symbols, and all unavoidable arrays of order at most 4. We also identify a number of general families of unavoidable arrays, which we conjecture to be a complete account of unavoidable arrays. Next, we investigate arrays with multiple entries in each cell, and identify a number of families of unavoidable multiple entry arrays. We also discuss fractional Latin squares, and their connections to unavoidable arrays.

1. Introduction

As is well known, proper edge colourings of complete balanced bipartite graphs correspond to Latin squares. Galvin’s theorem [6] determines a condition on how many colours must be available on each edge to ensure the existence of a proper edge colouring using only allowed colours at each edge of a general bipartite graph. In the edge colouring language, we investigate what conditions we must place on the lists of available colours if we want them to be slightly shorter than the length specified in Galvin’s theorem. In the terminology of Latin squares, we ask what symbols can be forbidden in which cells, and still allow a Latin square that does not violate any of these conditions.

The present investigation is in the same spirit as [5], where Brooks’ bound on the chromatic number, when odd cycles and Δ-cliques are excluded, is improved on to Δ − k for a range of k, by excluding more and more subgraphs. In our case, we find certain configurations of disallowed colours that make proper colouring impossible, but when these specific configurations are excluded, colouring is always possible.

We specify the forbidden symbols by entering them into an array, and we say that the array is avoidable if a Latin square as described exists.

The question of which n×n arrays are avoidable was posed by Häggkvist in 1989 [7]. It is not hard to produce examples of non-avoidable arrays, but no complete (nor even partial) characterisation is known. By results of Chetwynd and Rhodes [3], Cavenagh [1] and one of the present authors [2], all partial Latin squares of order at least 4 are avoidable, and there exist unavoidable partial Latin squares of order 2 and 3. We may therefore restrict our search for non-avoidable arrays to arrays that have at least one repeated entry in some row or column.

We shall start by proving a characterisation of all unavoidable arrays on exactly one or two symbols. Next, we list all small (orders 2, 3 and 4) minimal unavoidable arrays. We also discuss the question of which of these arrays are unavoidable when fractional Latin squares are allowed. We state some conjectures as to the set of all unavoidable arrays. We also investigate the avoidability of multiple entry arrays.

2. Preliminaries

An array, for our purposes, is a rectangular arrangement of symbols, with positions indexed by rows and columns, whose entries are symbols, with no implied algebraic structure, only the possibility of discerning between distinct symbols. We shall make a distinction between entries and symbols, namely that an entry is a symbol used in a certain position.

We shall use the term multiple entry array for arrays where the entries are sets of symbols, at least one of which has at least two members. The term “array” without the extra specification will always be an array where each entry is a single symbol (or a singleton set). We say that an n × n array is avoidable if for any set of n symbols there exists an n × n Latin square on these symbols, whose entries do not appear in the corresponding cells in the array. Unless otherwise stated, an n × n Latin square uses the symbols [n] = {1, …, n}.

Two arrays are isotopic if one can be transformed into the other by a 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. Two arrays are conjugate if one can be transformed into the other by freely exchanging the roles of rows, columns and symbols, and permuting elements within these classes. Obviously, two isotopic arrays are isomorphic, and two isomorphic arrays are conjugate. Also, all these relations are equivalence relations. Any conjugate of a (partial) Latin square is a (partial) Latin square, so when investigating avoidable (multiple entry) arrays, we need only consider distinct conjugacy classes.

Isotopies and isomorphies are generally quite possible to grasp. For conjugates, there is a geometric interpretation: Instead of a 2-dimensional n × n array, we may view an multiple entry array as a 3-dimensional arrangement of cubes, which on their top and bottom have a symbol printed, corresponding to an entry in the square that they are situated above. Also, a cube that bears symbol i floats at height i. On its front and back, the cube bears the row number that it is situated above, and on its left and right side it bears the column number. When observed from “above”, we will see symbols from the cubes above the cells in which they are entries. Conjugates can be observed by viewing this object from different directions. For an example, se Figure 1.

3. Arrays with one or two distinct symbols

It is reasonable to expect that unavoidable arrays using few symbols are not very common. In the next few results, we characterise those using exactly one or exactly two distinct symbols. It is obvious that an r×(n−r+1) rectangle filled with one single symbol makes for an unavoidable array. Any additional occurences of that symbol are not necessary, and can be removed, to achieve minimality. It would be conceivable, however, that there are other configurations using only one symbol that are also unavoidable. The next proposition, which is basically just a corollary to Hall’s theorem, rules this out.

Proposition 3.1. 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 one single symbol.

Proof. To produce a Latin square avoiding an array A with only the symbol 1, we need only find a diagonal of empty cells in the array. Here we can enter the symbol 1, and the completion to a Latin square is trivial, since no other symbols are prohibited. By Hall’s

Figure 1. A visualisation of conjugates

theorem, an array A using only one symbol has an empty diagonal iff for each set R of |R| = r rows, the number of columns C that have at least one empty cell in one of the rows in R is at least r.

In other words, an unavoidable array using only one symbol must have, for some r, a set R of r rows, where the empty cells in these rows occur in at most r − 1 distinct columns. Therefore, there is a set of at least n − (r − 1) columns having no 1:s in rows R. The intersection of R with these columns gives us our r × (n − r + 1) rectangle. □

When looking at unavoidable arrays with two distinct symbols, we find that we shall want to say when an array with one single symbol forces the use of that symbol in all of a set of cells or in at least one of a set of cells.

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

Proof. If we are forced to place the symbol 1 in cell (i, j) when avoiding A, it follows that adding a 1 to cell (i, j) results in an unavoidable array. By Proposition 3.1 the array now contains an r × (n − r + 1) rectangular subarray filled totally with the symbol 1. Finally, removing the added 1 from A results in the subarray claimed to exist. □

Lemma 3.3. Let A be an n × n avoidable array using only one symbol, 1. Suppose that any Latin square that avoids A must use the symbol 1 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 1, except for cells in T, which are empty.

Proof. We assume that there is no cell in S where the symbol 1 is forbidden, for then we simply remove it from S. We form T in the following way: If we fill all cells of S with ones, we have an unavoidable array, which must therefore contain an r × (n − r + 1) subarray B totally filled with the symbol 1. B intersects S, for the removal of the added 1:s in the cells of S would result in an avoidable array, and this can therefore not contain an r × (n − r + 1) subarray totally filled with 1:s. If we set T = B ∩ S we see that B covers T, and all cells of T are empty because all cells of S are, and T ⊂ S. If T were empty, A would not be avoidable. □

We are now in a position to prove a characterisation of unavoidable arrays on two distinct symbols.

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

Proof. Since we assume that neither the occurences of 1 nor 2 constitute an unavoidable array in themselves, we can assume that we may place the 1:s on a diagonal, respecting the constraints set by the 1:s in A_{2}. Then, no matter how these 1:s are placed, there is not enough room to place the 2:s. If it were possible to place the 2:s, we could easily fill in the rest of the Latin square, as there are no other symbols in A_{2}.

We draw the conclusion that for any diagonal of 1:s respecting the forbidden 1:s in A_{2}, A_{2} contains an r × (n − r + 1) subarray almost completely filled with the symbol 2, except possibly for a set of cells S. S is such that the diagonal of 1:s uses all cells in S, and S has at least one empty cell. This follows from Proposition 3.1.

What is this set S? For starters, no two cells of S lie in the same row or column, since it is contained in a diagonal. Next, if |S| ≥ 2 for some diagonal of 1:s, we could reform the diagonal so that we did not use 1:s in the empty cells of a nearly full r × (n − r + 1) rectangular subarray. For |S| = 2 this procedure is illustrated in Figure 2. We read “a/b” as a being forbidden, and b being used in that cell. ∅ indicates an empty cell.

\begin{matrix}∅/1 & … & 2/∅ \\ … & & … \\ 2/∅ & … & ∅/1 \end{matrix}  →  \begin{matrix}∅/∅ & … & 2/1 \\ … & & … \\ 2/1 & … & ∅/∅ \end{matrix}

Figure 2. Reforming S

We see therefore that there are single cells, namely the S, where the symbol 2 must be used. This we learn from Lemma 3.2. If we go through all the possible diagonals of 1:s, we see that the set of cells M_{2}, where the symbol 2 must be used, forced by the 2:s alone, with no help from the 1:s is not empty. M_{2} forms part of a diagonal, for if there were two cells in M_{2} in the same row (or column), then we would be forced to place the symbol 2 twice in the same row (or column), and that would mean that the 2:s in themselves would constitute an unavoidable array. We also have that M_{2} forms part of any diagonal of 2:s.

Also, any diagonal of 1:s intersects M_{2}, by the way it is defined. By exchanging the roles of 1 and 2 in the above argument, we also find a set of cells M_{1}, where the symbol 1 must be used, that intersects any possible diagonal of 2:s. We claim that M_{1} ∩M_{2} ≠ ∅. Any cell in M_{1} ∩ M_{2} is an example of an empty cell that lies in the intersection of an r × (n − r + 1) array nearly full of 1:s and an (n − r + 1) × r array nearly full of 2:s, so if we prove the claim we are finished.

We know that any diagonal of 1:s intersects M_{2} and vice versa. This implies that there are no distinct cells of M_{1} and M_{2} in the same row or column. Also, Lemma 3.3 tells us that there is a nonempty set T ⊂ M_{2} such that there is an r × (n − r + 1) subarray B that covers T and is completely filled with 1:s except for the cells of T.

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

\begin{matrix}1/∅ & … & ∅/2 \\ … & & … \\ ∅/2 & … & 1/∅ \end{matrix}  →  \begin{matrix}1/2 & … & ∅/∅ \\ … & & … \\ ∅/∅ & … & 1/2 \end{matrix}

Figure 3. Reforming T

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

Unavoidable arrays with exactly one symbol are easily grasped. In Figure 4, we see, however, that B_{5,2} is not minimal, for it contains B_{5,1} as a subarray. B_{5,3} is minimal. Theorem 3.4 states that the minimal unavoidable arrays with 2 distinct symbols are exactly the arrays of type B, with the exception of B_{n,2} for all n.

B_{5,1}: 1 1 1 1 2 2 2 2 B_{5,2}: 1 1 1 1 1 1 1  2 2 2 2 2 2 2 B_{5,3}: 1 1 1 1 1 1 1 1  2 2 2 2 2 2 2 2

Figure 4. All 5 × 5 arrays of type B

For reference, we record in the following two lemmas when a 2-symbol array forces the use of one of these symbols in all of or at least one of a specified set of empty cells, and remark that the general case when the cells in which a 1 or 2 is forced are not empty is considerably harder to make sense of.

Lemma 3.5. Let A be an n × n avoidable array on symbols 1 and 2, and suppose that cell c is empty and any Latin square that avoids A uses a 1 in cell c. Then one of the following holds.

a. There is an r × (n − r + 1) subarray R_{1} covering c, all of whose cells except c are

filled with forbidden 1:s. b. There are two subarrays R_{1} and R_{2}, c ∈ R_{1}, R_{1} ∩ R_{2} = e, cell e is empty, e ≠ c, R_{1} \ {c, e} is filled with forbidden 1:s, and R_{2} \ {e} is filled with forbidden 2:s.

Proof. Placing an additional forbidden 1 in cell c produces an unavoidable array, B. If B is unavoidable onn account of the 1:s alone, we have case a., by Proposition 3.1. If both 1:s and 2:s play a part in making B unavoidable, then by Theorem 3.4 we have case b. □

Lemma 3.6. Let A be an n × n avoidable array on symbols 1 and 2, and S a set of empty cells of A. Suppose that any Latin square that avoids A uses a 1 in at least one of the cells in S.

Then we can find a non-empty subset T ⊂ S and an r × (n − r + 1) subarray R_{1} of A that covers T and has the following properties: In each cell of R_{1} \ T either we are forced to use a 2, or we were forbidden to use a 1 there.

Proof. We may assume that we are not forced to use a 2 in any cell of S, for such cells we may simply remove from S. If there is a single cell c ∈ S where we are forced to use a 1, we may take T = {c} and be done by Lemma 3.5. By Lemma 3.3, if the symbol 1 by itself forces the use of a 1 in at least one of a set of cells, we are finished. If interplay between the 1:s and the 2:s is required, we construct T in the following way:

All cells of S are empty, and if we fill the cells of S with forbidden 1:s, we will have an unavoidable array with two distinct symbols. If this new array is unavoidable on account of the 1:s alone, we know that we have filled an r × (n − r + 1) subarray R_{1} with forbidden 1:s, and T = S ∩ R_{1} will do for our T.

If, on the other hand, both symbols in the new array interplay to make it unavoidable, Theorem 3.4 gives that A contains two subarrays R_{1} and R_{2} with the properties stated in that theorem. We know that R_{1} ∩ S ≠ ∅, for if this were not the case, we could remove all the 1:s from S and still have an unavoidable array, contrary to our assumption on A. We set T = R_{1} ∩ S. Then obviously T ⊂ S and T ≠ ∅. Cells of R_{1} \ T either hold forbidden 1:s or we are forced to use 2:s there. □

We conclude this section by properly defining arrays of type A and B, and again noting that we have a complete characterisation of unavoidable arrays on one or two symbols. We state the characterisation as a theorem.

Definition 3.7. We denote by A_{n,r} the n × n unavoidable 1-symbol array that has an r × (n − r + 1) subarray filled with that symbol.

By B_{n,r} we denote the n × n unavoidable 2-symbol array that has an r × (n − r + 1) subarray R_{1} filled with 1:s except for one cell c, and an (n − r + 1) × r subarray R_{2} filled with 2:s except for the cell c = R_{1} ∩ R_{2}.

Theorem 3.8. Let M be a minimal n×n unavoidable array on one or two symbols. Then M ∈ \{A_{n,1}, …, A_{n,⌈ \frac{n}{2} ⌉}, B_{n,1}, …, B_{n,1}, B_{n,3}, …, B_{n,⌈ \frac{n}{2} ⌉}\}.

4. Investigating small arrays

By Proposition 3.1 and Theorem 3.4, the only minimal unavoidable arrays on one (labelled A with indexing subscripts) or two symbols (labelled B with indexing subscripts) for 2 ≤ n ≤ 4 are, up to isomorphy, those given in Figure 5. Note that these include all (both!) unavoidable 2 × 2 minimal unavoidable arrays. The label D is for a family of unavoidable arrays using from 1 to n symbols, the construction of which should be obvious when inspecting Figure 7 in conjunction with Figure 5.

All minimal non-avoidable 3 × 3 arrays on 3 symbols (up to isomorphy), generated by computer, are given in Figure 6. The minimal unavoidable non-isomorphic 4 × 4 arrays on

\begin{matrix}A_{2,1} : \\ D_{2,1} \end{matrix}  1 1  \begin{matrix}B_{2,1} : \\ D_{2,2} \end{matrix}  1 2  \begin{matrix}A_{3,1} : \\ D_{3,1} \end{matrix}  1 1 1

A_{3,2}:  1 1 1 1  \begin{matrix}B_{3,1} : \\ D_{3,2} \end{matrix}  1 1 2 2  \begin{matrix}A_{4,1} : \\ D_{4,1} \end{matrix}  1 1 1 1

A_{4,2}: 1 1 1 1 1 1  \begin{matrix}B_{4,1} : \\ D_{4,2} \end{matrix}  1 1 1 2 2 2

Figure 5. Minimal unavoidable arrays on one or two symbols

at least 3 symbols corresponding to these are presented in Figure 7. Unexpected additions to the list of 4 × 4 unavoidable arrays, all using 4 symbols, are given in Figure 8.

These are minimal in the sense that the removal of any entry results in an avoidable array. The list is complete in the sense that any unavoidable array contains one of them as a subarray. We will refer our unavoidable arrays as being of type A through D or S, as listed. Types A – D are evidently parts of larger families of unavoidable arrays, that have members for each order. That “type” S generalises to any order is not as clear. In fact, we conjecture that the arrays of type S presented here are exceptional examples, hence the label S for ‘Sporadic’. This conjecture will be articulated more precisely below.

\begin{aligned}C_{3,1}: & 1 2 3 1 2 & C_{3,2}: & 1 1 1  3 2 & \begin{matrix}C_{3,3} : \\ D_{3,3} \end{matrix} & 1 2 1 2 3 \\ & & S_{3,1}: & 1 2 3 1 3 2 & S_{3,2}: & 1 2 3 3  1 2 1 \end{aligned}

Figure 6. All minimal unavoidable 3 × 3 arrays on 3 symbols

In Figure 6 we find an old aquaintance from [7], namely S_{3,1}, which was identified as the only known example of an unavoidable row-latin array with empty last row.

The list of unavoidable 4 × 4 arrays in Figures 5 through 8 was generated by computer in the following manner:

First, the set of all avoidable arrays on the symbol ‘1’ were generated, and reduced with respect to isomorphism using Brendan McKay’s isomorphism package Nauty [9]. Next, for each of the generated 1-symbol arrays, forbidden 2:s were added, in each case fewer than or equal to the number of already present 1:s. Another run of Nauty reduced this list. In the same manner, symbols 3 and 4 were added.

This final reduced list was then tested for avoidability and minimality using the SATsolver UMSAT developed at Umeå university.

\begin{matrix}C_{4,1}: & 1 2  3 1 2  3 1  1 2 2 & C_{4,2}: & 1 1 1 1  3 1  3 2 2 & \begin{matrix}C_{4,3} : \\ D_{4,3} \end{matrix} & 1 2 1 2 1 2 3 3 \\ D_{4,4}: & 1 2 3 1 2 3 1 2 3 4 & S_{4,1}: & 1 1 2 3 1 1 3 2 2 2 3 3 & S_{4,2}: & 1 2 2 3 3 4 4 1 3 4 4 1 2 1 1 \end{matrix}

Figure 7. Corresponding minimal unavoidable 4 × 4 arrays

S_{4,3}: 1 1  2 1 1  2 3 2 2 4 2 4 2 3 S_{4,4}: 1 1  2 1 1  2 3 3 2 4 4 4 2 3 S_{4,5}: 1 1 1 1 2 2 2 3 2 4 4 2 2 3

S_{4,6}: 1 1 1 1 2 2 3 3 2 4 4 4 2 3 S_{4,7}: 1 1 1 1 1  2 2 3 2 4 4 2 2 3 S_{4,8}: 1 1 1 1 1  2 3 3 2 4 4 4 2 3

S_{4,9}: 1 1 1 1 3 4 3 2 2  2 2 3 3 4

Figure 8. All minimal unavoidable 4 × 4 arrays not included in Figures 5 or 7

We note that among the arrays in this section, those labelled with C_{n,1}, C_{n,2}, C_{n,3} and D_{n,r} can be generalised to any n, and that we have found no general construction to extend any of the arrays of type S to arrays of general size. We phrase this as a proposition.

Proposition 4.1. For n ≥ 3 there exist at least three distinctive types of unavoidable arrays on three symbols, namely C_{n,1}, C_{n,2} and C_{n,3}. Also, for any r ≤ n there exist unavoidable array on r distinct symbols, namely the D_{n,r}.

5. Multiple entry arrays

In [4] a rough counting method yielded some general results on avoidable multiple entry arrays, but here we aim for precise descriptions of the border between avoidable and unavoidable.

5.1. Entries in only one or two rows. If we allow ourselves to forbid more than one symbol in each cell of an array, our list of unavoidable arrays will evidently grow longer. Figure 9 shows the sole addition to the list of 2 × 2 arrays, and the general form of unavoidable multiple entry arrays with only one non-empty cell.

Taking conjugates of single entry arrays on one or two symbols, we immediately get a characterisation of unavoidable multiple entry arrays where all entries lie in the first

a_{2,1}: 1,2  a_{n,1} : 1,…,n . . . . . .  . . . . . .

Figure 9. Unavoidable multiple entry arrays using only one cell

two rows. We will not reformulate our characterisation explicitly, but rather present two illustrating exemples, in Figure 10.

1,2,3 1,2,3 1,2,3  1,2,3 1,2,3 1,2 4,5 3,4,5 3,4,5

Figure 10. Unavoidable multiple entry arrays using only one or two rows

5.2. Entries only on a diagonal. Making use of the following characterisation by G. J. Chang, cited (and again proved) in [8], of completable partial Latin squares having all their entries on a diagonal, we can characterise all unavoidable multiple entry arrays with entries only on a diagonal.

Theorem 5.1. Let D be an n × n array with entries on a generalised diagonal. D is completable iff no symbol occurs exactly n − 1 times.

When applied to avoidability, Theorem 5.1 implies that if we exclude the trivial case of when all symbols are forbidden in some cell, a multiple entry array with entries only on the diagonal is unavoidable exactly when it forces us to use one symbol exactly n − 1 times, and a different symbol in the last cell on the diagonal. It may seem that a direct description of the unavoidable arrays presently considered is trivial, but it turns out that there is one twist to the story. It is fairly obvious that if symbols, say, 1, …, (n−1) are all forbidden in the n − 1 first cells along the diagonal, and symbol n is fobidden in the last cell, then we have an unavoidable array, by Theorem 5.1, but, as made clear in Figure 11, there is at least one other array that is unavoidable.

c_{3,1}: 1,2 1,3 1  \begin{matrix}c_{3,3} : \\ d_{3,3} \end{matrix}  1,2 1,2 3

Figure 11. 3 × 3 unavoidable multiple entry arrays with entries only on the diagonal

We might fear at this stage that things will be complicated, or at least that c_{3,1} could be the smallest member of an infinite family, but this is not the case, as made clear by the following proposition, which concludes our characterisation, and establishes that c_{3,1} is a rare bird. We denote by d_{n,n} the conjugate of D_{n,n} obtained by exchanging the roles of columns and symbols.

Proposition 5.2. Let n ≥ 4 and A be an unavoidable n × n multiple entry array with entries only on the main diagonal, and at most n−1 entries in each cell. Then A contains an array that is isomorphic to d_{n,n}.

Proof. Given an array A with entries only on the diagonal, we might try to avoid it and see what goes wrong. We start by taking all cells where exactly n − 1 symbols are forbidden, and entering the mising symbol in our proposed Latin square L that would avoid A. If it should be the case that we thereby use at least three different symbols, then A was avoidable, by Theorem 5.1. Likewise, if we used two symbols each at least twice, A was avoidable.

After filling in all these forced symbols, we may have some cells where there is some flexibility. If there are none, by Theorem 5.1, L must have one symbol exactly n − 1 times and a different symbol exactly once. Since there was no flexibility in entering the symbols in L, it can be easily seen that A contains an isomorphic copy of D_{n,n}.

If there are two or more cells with more than one possible choices, we simply chose at least two symbols, which may or may not be alike, that weren’t already used n − 2 times.

If there is exactly one cell with more than one possible choice, then A can only be unavoidable if we are forced to use a symbol previosly used exactly n − 2 times, or are prevented from using a symbol used exactly n − 1 times. Since n ≥ 4, n − 2 ≥ 2, and a symbol used n − 2 times is therefore unique. In either of the two cases, it can easily be checked that A contains an isomorphic copy of d_{n,n}. □

We see now why c_{3,1} is unavoidable: Two different symbols are forced into place in two cells on the diagonal, and the choice we have in the last cell is which of the two to repeat. However, since n − 2 = 1 in this case, either choice will result in the configuration forbidden by Theorem 5.1.

5.3. Multiple entry 3 × 3 arrays. For n = 3, the list of unavoidable multiple entry arrays, produced by case analysis by hand, is presented in Figure 12. This case analysis isn’t too demanding, if one starts with fixing symbols 1 and 2 in cell (1, 1), and observing that this implies that no minimal unavoidable array can ever hold another forbidden 3 in some other cell in the first row or column.

The arrays in Figure 12 are labelled such that lower case a, b, c, d, s are conjugates of arrays labelled with upper case A, B, C, S. The rest of the arrays are paired as conjugates, so that for instance x_{3,1} is conjugate to x_{3,2}.

5.4. Multiple entry 4 × 4 arrays on two symbols. The 4 × 4 multiple entry arrays in Figures 13 through 16 show all nonisomorphic 4 × 4 multiple entry arrays on two symbols, i.e. where there is at least one cell in which both symbols are forbidden. The list was generated by computer in the following manner:

First, the set of all avoidable 1-symbol arrays (with the symbol ‘1’) were generated, and reduced with respect to isomorphism using Nauty. Next, for each of the generated 1-symbol arrays, forbidden 2:s were added, in each case fewer than or equal to the number of already present 1:s. Another run of Nauty reduced this list. This final reduced list was then tested for avoidability and minimality using UMSAT.

5.4.1. Type I unavoidable multiple entry 4 × 4 arrays on two symbols. The alert reader will notice that the mechanism that makes all the arrays in Figure 13 unavoidable is that there exists a single cell in which the forbidden 1:s force us to place a 1, and the forbidden 2:s then forces the use of a 2 in the same cell.

5.4.2. Type II unavoidable multiple entry 4 × 4 arrays on two symbols. In Figure 14, the list continues, but the mechanism is now a set of two cells in each of which the forbidden

\begin{matrix}a_{3,1}: & 1,2,3 & a_{3,2}: & 1,2 1,2 & \begin{matrix}b_{3,1} : \\ d_{3,2} \end{matrix} & 1,2 3 3 \\ c_{3,1}: & 1,2 1,3 1 & c_{3,2}: & 1,2 1 3 2 & \begin{matrix}c_{3,3} : \\ d_{3,3} \end{matrix} & 1,2 1,2 3 \\ s_{3,1}: & 1,2 1 2 2 1 & x_{3,1}: & 1,2 1 2 3 & x_{3,2}: & 1,2 1 1 2 \\ y_{3,1}: & 1,2 1 1,3 & y_{3,2}: & 1,2 1 2 1 & z_{3,1}: & 1,2 1 3 1 \\ z_{3,2}: & 1,2 1 1 2 & w_{3,1}: & 1,2  1 3 2 & w_{3,2}: & 1,2  1 3 1 \end{matrix}

Figure 12. Minimal unavoidable 3 × 3 multiple entry arrays

1,2 1,2 1,2  1 1 1 1,2 1,2  2  1 1 1,2 1 1 2 2 1 1 1 1,2 1,2 2 2 2  1 1 1 1 1,2  2 2 2 2  1 1,2 1,2 1 1,2 2 2

Figure 13. Type I unavoidable 4 × 4 multiple entry arrays on two symbols

1:s force us to place a 1, and the forbidden 2:s force us to place at least one 2 in these cells.

Arrays of types I and II can, at least in principle, be described in full for any array size by applying Theorem 3.4.

5.4.3. Type III unavoidable multiple entry 4 × 4 arrays on two symbols. The unavoidable arrays in Figure 15 are a bit more complicated. They fall under neither of the two above descriptions, but instead, there is some essential interplay between the two symbols in forcing the use of certain symbols in certain cells, eventually leading to a conflict. If we take the first of the arrays in Figure 15 as an example, we see that a 1 is forced in cell (1, 4), then 2:s are forced in cell (3, 1) and (4, 4), then a 1 is forced in (3, 1) and consecutively in (2, 3). After this, a 2 is forced in (4, 3), which is a conflict with the 2 already forced in (4, 4).

1 1,2 1,2 1 1,2  2  1 1 1,2 1 1  2 2 2  1 1 1 1,2 1,2 1,2  2

1 1 1 1,2 1,2 1 2 2  1,2 1 1,2 1,2 1 1 2  1 1 1 1,2 1 1,2  2 2

1 1 1 1,2 1  2 1 2 2  1,2 1,2 1 1 1 2  2

Figure 14. Type II unavoidable 4 × 4 multiple entry arrays on two symbols

If we apply the same typology to the list of unavoidable multiple entry arrays in Figure 12, we see that arrays a_{3,2} and y_{3,2} are of type I, arrays x_{3,2} and z_{3,2} of type II and the array s_{3,1} does not belong to any of the three types.

1 1 1,2 1  2 2 1,2 2  1,2 1,2 1 1,2  2 1 2  1,2 1,2 1 1,2  2 1  2

Figure 15. Type III unavoidable 4 × 4 multiple entry arrays on two symbols

S_{4,G}: 1,2 1,2 1,2  1,2 1,2 1,2  S_{4,{10}}: 1,2 1,2 1,2  1 2 1,2 2 1

Figure 16. The two remaining unavoidable 4×4 multiple entry arrays on two symbols

5.4.4. The two remaining unavoidable multiple entry 4 × 4 arrays on two symbols. We will return to S_{4{10}} in the section on fractional relaxations. For now, we only note that no single symbol is forced in place in any cell, and that there is no obvious mechanism that makes S_{4{10}} unavoidable.

Regarding S_{4,G}, however, there is an interesting thing to note, namely that it has only the entries {1, 2} in each non-empty cell. Since we only need to find a diagonal of 1:s and a diagonal of 2:s in order to be sure that an array on symbols 1 and 2 is avoidable, in this case we can rephrase the problem as finding a 2-factor (a 2-regular subgraph) in a certain bipartite graph. The fact that only {1, 2} occur as entries in the array means that the edges are either free to use for either diagonal, or that they are not available at all.

1,2 1,2 1,2  1,2 1,2 1,2  →

Figure 17. Type III unavoidable 4 × 4 multiple entry arrays on two symbols

When this reformulation is possible, which is the case exactly when all non-empty cells have exactly the same entries, we can use results from graph theory to characterise the unavoidable arrays. For the 2-factor case (i.e. when all entries are {1, 2}) we have the following theorem from [11], where N(S) denotes the neighbour set of the set S ⊂ V.

Theorem 5.3. Let B = (V, E) be a bipartite graph. Then B has a 2-factor if and only if |N(S)| ≥ |S| for each independent set S.

For arrays with all entries {1, … k}, which in the graph theoretical formulation amounts to finding k-factors in balanced bipartite graphs, we refer the reader to [10].

5.5. A padding construction. Given an n×n unavoidable array A on t symbols, there is a simple construction of an unavoidable (n + r) × (n + r) multiple entry array for any t ≥ r. The construction is illustrated in Figure 18, where B signifies an r × r array that is entirely empty, and C signifies an r ×n array, where symbols 1, …, r are forbidden in each cell. As an illustrating example, in the same figure is presented the array S_{4,{10}} padded with two rows.

\begin{aligned}B & C \\ & A \end{aligned}  1,2 1,2 1,2 1,2 1,2 1,2 1,2 1,2 1,2 1,2 1,2  1 2 1,2 2 1

Figure 18. The general form of a padding construction, and S_{4,{10}} padded with two rows.

The added symbols in the subarray C can be distributed more evenly by placing half of them, or rather ⌈\frac{r}{2}⌉ of them, in C, and the rest of them in the subarray below B. For instance, an unavoidable 2-symbol single entry array can be padded in such a way that it is still a single entry array. This may seem to contradict Theorem 3.4, but the construction actually again yields an unavoidable array with the structure described in that theorem.

6. A fractional relaxation

The business of producing Latin squares, with or without constraints such as those presently considered, can be viewed as an instance of integer programming. By relaxing the integer constraint in the way that we allow fractional values in our solution vector, we may produce a corresponding linear programming instance. The solution to this linear program,

1 2 3 1 3 2 → \begin{matrix}\frac{1}{2}(2, 3) & \frac{1}{2}(1, 3) & \frac{1}{2}(1, 2) \\ \frac{1}{2}(2, 3) & \frac{1}{2}(1, 2) & \frac{1}{2}(1, 3) \\ 1 & \frac{1}{2}(2, 3) & \frac{1}{2}(2, 3) \end{matrix}

1 2 3 3  1 2 1 → \{ \begin{matrix}\frac{1}{2}(2, 3) & \frac{1}{2}(1, 3) & \frac{1}{2}(1, 2) \\ \frac{1}{2}(1, 2) & \frac{1}{2}(1, 2) & 3 \\ \frac{1}{2}(1, 3) & \frac{1}{2}(2, 3) & \frac{1}{2}(1, 2) \end{matrix} ; \begin{matrix}\frac{1}{2}(2, 3) & \frac{1}{2}(1, 3) & \frac{1}{2}(1, 2) \\ \frac{1}{2}(1, 2) & \frac{1}{2}(1)\frac{1}{6}(2)\frac{1}{3}(3) & \frac{1}{3}(2)\frac{2}{3}(3) \\ \frac{1}{2}(1, 3) & \frac{5}{6}(2)\frac{1}{6}(3) & \frac{1}{2}(1)\frac{1}{6}(2)\frac{1}{3}(3) \end{matrix}

Figure 19. S_{3,1} and S_{3,2} with fractional solutions LS_{3,1} and LS_{3,2}.

if it exists, we call a fractional Latin square. Since all constraints and input values are integers, any solution will have rational coefficients.

Without taking the detour via linear programming, we may instead view a fractional Latin square as a square array, in whose cells we have specified rational weights for all the symbols, in such a manner that weights in a single cell sum to 1, and that the weight of a single symbol sums to 1 in each row and column. Obviously, a Latin square is a fractional Latin square. We shall call an array A fractionally unavoidable if there exists no fractional Latin square F such that if symbol σ is forbidden in cell (i, j) of A, the weight of σ in cell (i, j) of F is zero.

Definition 6.1. A porous array is an unavoidable array that is fractionally avoidable.

It is fairly obvious that arrays of types A, B, C and D are fractionally unavoidable as well as unavoidable, and the multiple entry arrays of types x through w in Figure 12 are also fractionally unavoidable, as is easily checked. We shall use the notation \frac{1}{p}(σ, τ) to indicate that symbols σ and τ are each used with a weight of \frac{1}{p} in the cell in question, and the notation \frac{1}{p}(σ) to indicate that symbol σ is used with a weight of \frac{1}{p} in the cell in question.

Proposition 6.2. LS_{3,1} is the unique fractional Latin square avoiding S_{3,1}.

Proof. (Sketch) In Figure 19 we see that the 1 in the lower left corner of LS_{3,1} is forced in place by the two 1’s in S_{3,1}. Also, if we specify that a fraction \frac{1}{p} of a 1 be used in the middle cell, this immediately determines the rest of the use of symbol 1, and consequently of symbols 2 and 3. For example, symbol 3 must be used \frac{1}{p} times both in cell (3, 2) and (3, 3), thus forcing p = 2. Therefore LS_{3,1} is unique. □

LS_{3,2}, however, is not unique. To see this, assume that \frac{1}{p} of a 2 is used in the upper left hand corner. This determines both the first row and the first column. It also forces the use of 1 − \frac{1}{p} of a 1 in cell (2, 2) and \frac{1}{p} of a 1 in cell (2, 2), thereby fixing p = 2. Now, suppose \frac{1}{q} of a 3 is used in cell (2, 3), and consequently 1 − \frac{1}{q} of a 2 in that cell. Then q ≥ 2, for otherwise we cannot fit enough 3:s in row 2. However, q can take any value in the range \frac{1}{2} ≤ q ≤ 1.

In Figures 20 through 23, a whole symbol is used only where forced. Among the multiple entry arrays in Figure 12, only s_{3,1} is fractionally avoidable, and it is also a conjugate of

1 1 2 3 1 1 3 2 2 2 3 3 → \begin{matrix}\frac{1}{2}(2, 4) & \frac{1}{2}(3, 4) & \frac{1}{2}(1, 3) & \frac{1}{2}(1, 2) \\ \frac{1}{2}(3, 4) & \frac{1}{2}(2, 4) & \frac{1}{2}(1, 2) & \frac{1}{2}(1, 3) \\ \frac{1}{2}(1, 2) & \frac{1}{2}(1, 2) & \frac{1}{2}(3, 4) & \frac{1}{2}(3, 4) \\ \frac{1}{2}(1, 3) & \frac{1}{2}(1, 3) & \frac{1}{2}(2, 4) & \frac{1}{2}(2, 4) \end{matrix}

1 2 2 3 3 4 4 1 3 4 4 1 2 1 1 → \begin{matrix}\frac{1}{2}(2, 3) & \frac{1}{2}(1, 4) & \frac{1}{2}(3, 4) & \frac{1}{2}(1, 2) \\ \frac{1}{2}(1, 4) & \frac{1}{2}(2, 3) & \frac{1}{2}(1, 2) & \frac{1}{2}(3, 4) \\ \frac{1}{2}(2, 4) & \frac{1}{2}(1, 3) & \frac{1}{2}(1, 2) & \frac{1}{2}(3, 4) \\ \frac{1}{2}(1, 3) & \frac{1}{2}(2, 4) & \frac{1}{2}(3, 4) & \frac{1}{2}(1, 2) \end{matrix}

Figure 20. S_{4,1} and S_{4,2} with fractional solutions LS_{4,1} and LS_{4,2}.

1 1  2 1 1  2 3 2 2 4 2 4 2 3 1 1  2 1 1  2 3 3 2 4 4 4 2 3 \} → \begin{matrix}\frac{1}{2}(2, 4) & \frac{1}{2}(3, 4) & \frac{1}{2}(1, 3) & \frac{1}{2}(1, 2) \\ \frac{1}{2}(3, 4) & \frac{1}{2}(2, 4) & \frac{1}{2}(1, 2) & \frac{1}{2}(1, 3) \\ \frac{1}{2}(1, 2) & \frac{1}{2}(1, 2) & \frac{1}{2}(3, 4) & \frac{1}{2}(3, 4) \\ \frac{1}{2}(1, 3) & \frac{1}{2}(1, 3) & \frac{1}{2}(2, 4) & \frac{1}{2}(2, 4) \end{matrix}

Figure 21. S_{4,3} and S_{4,4} with a common fractional solution LS_{4,34}.

\begin{matrix}1 1 1 1 2 2 2 3 2 4 4 2 2 3 & 1 1 1 1 2 2 2 3 2 4 4 2 2 3 \\ 1 1 1 1 1  2 2 3 2 4 4 2 2 3 & 1 1 1 1 1  2 3 3 2 4 4 4 2 3 \end{matrix} \} → \begin{matrix}\frac{1}{2}(3, 4) & \frac{1}{2}(3, 4) & 2 & 1 \\ \frac{1}{2}(2, 3) & \frac{1}{2}(2, 4) & 1 & \frac{1}{2}(3, 4) \\ \frac{1}{2}(1, 4) & \frac{1}{2}(1, 2) & \frac{1}{2}(3, 4) & \frac{1}{2}(2, 3) \\ \frac{1}{2}(1, 4) & \frac{1}{2}(1, 3) & \frac{1}{2}(3, 4) & \frac{1}{2}(2, 4) \end{matrix}

Figure 22. S_{4,5} to S_{4,8} with a common fractional solution LS_{4,5678}.

1 1 1 2 2 2 1 3 4 3 2 3 3 4 → \begin{matrix}\frac{1}{2}(2, 4) & \frac{1}{2}(2, 3) & \frac{1}{2}(3, 4) & 1 \\ \frac{1}{2}(1, 4) & \frac{1}{2}(1, 3) & 2 & \frac{1}{2}(3, 4) \\ \frac{1}{2}(2, 3) & \frac{1}{2}(1, 4) & \frac{1}{2}(1, 3) & \frac{1}{2}(2, 4) \\ \frac{1}{2}(1, 3) & \frac{1}{2}(2, 4) & \frac{1}{2}(1, 4) & \frac{1}{2}(2, 3) \end{matrix}

Figure 23. S_{4,9} with a fractional solution LS_{4,9}.

the only known unavoidable row-latin but not partially latin array, S_{3,1}, which we have mentioned earlier.

Conjecture 6.3. There exists a k ∈ ℕ such that for all n ≥ k there are no porous single entry n × n arrays. In fact, k = 5 may be such a k.

1,2 1,2 1,2 1 2 1,2 2 1 → \{ \begin{matrix}3 & 4 & \frac{1}{2}(1, 2) & \frac{1}{2}(1, 2) \\ 4 & \frac{1}{2}(1, 2) & \frac{1}{2}(2, 3) & \frac{1}{2}(1, 3) \\ \frac{1}{2}(1, 2) & 3 & \frac{1}{2}(1, 4) & \frac{1}{2}(2, 4) \\ \frac{1}{2}(1, 2) & \frac{1}{2}(1, 2) & \frac{1}{2}(3, 4) & \frac{1}{2}(3, 4) \end{matrix} ; \begin{matrix}\frac{1}{2}(3, 4) & \frac{1}{2}(3, 4) & \frac{1}{2}(1, 2) & \frac{1}{2}(1, 2) \\ \frac{1}{2}(3, 4) & \frac{1}{2}(1, 2) & \frac{1}{2}(2, 3) & \frac{1}{2}(1, 4) \\ \frac{1}{2}(1, 2) & \frac{1}{2}(3, 4) & \frac{1}{2}(1, 4) & \frac{1}{2}(2, 3) \\ \frac{1}{2}(1, 2) & \frac{1}{2}(1, 2) & \frac{1}{2}(3, 4) & \frac{1}{2}(3, 4) \end{matrix}

Figure 24. S_{4,{10}} with fractional solutions.

Note that this conjecture says nothing about what the unavoidable arrays are — there may well surface unavoidable arrays other than types A to D.

As for multiple entry arrays, all arrays in Figures 5.1 and 12 except s_{3,1} are fractionally unavoidable, while s_{3,1}, being a conjugate of a sporadic (single entry) array is also fractionally avoidable. The arrays in Figures 13 and 14 are all fractionally unavoidable, but in Figure 15 there is one exception, labelled S_{4,{10}}, which is avoided, for instance, by the fractional Latin squares shown in Figure 6, where the 1:s and 2:s are uniquely determined, but the 3:s and 4:s allow for some flexibility.

Linear combinations of the two fractional Latin squares presented in Figure 24 also avoid S_{4,{10}}, so here too, there is no uniqueness.

One might ask whether there exist porous multiple entry arrays of any order. Using the construction in Section 5.5 and padding s_{3,1} or S_{4,{10}}, we have the following proposition, where the inclusion of the epithet ‘multiple entry’ is essential.

Proposition 6.4. There exist porous multiple entry arrays of any order n ≥ 3.

7. Concluding remarks

Why do the sporadic unavoidable arrays of order 3 and 4 exist? They seem to break the nice pattern the other unavoidable single entry arrays make out. Is the key ingredient perhaps that they use (almost) all available symbols, each one a large number of times, or do they exist because 3 and 4 are such small numbers? In the opinion of the present authors, the second explanation is the correct one. For instance, we believe the list of arrays in Figure 25 to be a complete list of minimal unavoidable 5 × 5 arrays on at least three symbols, up to isomorphism.

In general, we would like to propose the following conjecture.

Conjecture 7.1. For n ≥ 5, the following is a complete (up to isomorphy) list of minimal unavoidable n × n single entry arrays: A_{n,1}, …, A_{n,⌈n/2⌉}, B_{n,1}, B_{n,3}, …, B_{n,⌈n/2⌉}, C_{n,1}, C_{n,2}, C_{n,3}, D_{n,4}, …, D_{n,n}.

In particular, we conjecture that any minimal unavoidable array on at least k ≥ 5 symbols is a D_{n,k}. A more tractable problem might be the following: If the only minimal unavoidable arrays on k symbols are the D_{n,k}, show that the same holds for k + 1 ≤ n.

Conjecture 7.1 may seem rash, and we concede that it is based mainly on the fact that no other families of unavoidable single entry arrays are known. As mentioned in the introduction, however, there are phenomena that provably only occur for very small arrays, for instance unavoidable partial Latin squares, which exist for orders 2 and 3 only

\begin{matrix}C_{5,1}: 1 2  3 1 2  3 1 2  3 1  1 1 2 2 2 & C_{5,2}: 1 1 1 1 1  3 1  3 1  3 2 2 2 & \begin{matrix}C_{5,3}: \\ D_{5,3} \end{matrix} 1 2 1 2 1 2 1 2 3 3 3 \\ D_{5,4}: 1 2 3 1 2 3 1 2 3 1 2 3 4 4 & D_{5,5}: 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 5 \end{matrix}

Figure 25. Minimal unavoidable 5 × 5 arrays on at least 3 symbols, that belong to known families

(see [3, 1, 2]). It is not unreasonable that a similar result might hold for unavoidable single entry arrays in general. Another instance where small arrays cause problems, but larger arrays are more well-behaved is row-latin squares with empty last row. Häggkvist [7] found a single unavoidable row-latin square with empty last row, labelled S_{3,1} in the present article, and proved that no such arrays exist for n = 2^{k}. In other words, there are other phenomena in this area of research where there exist som anomalous small cases, but for larger size arrays, everything works as expected. Conjecture 7.1 is therefore not as poorly grounded as one might believe at first glance.

By Proposition 3.1 and Theorem 3.4, all unavoidable single entry arrays on one or two symbols are characterised, and the present authors believe that three symbols should also be manageable, even though Conjecture 7.1 may be off mark. Hopefully, this issue will be revisited soon.

Where multiple entry arrays are concerned, we are convinced that the general problem of characterising all unavoidable arrays is certainly an intractable problem, but that there are some interesting polynomial special instances. We note also that Proposition 3.1 and Theorem 3.4 yield polynomial algorithms for recognising unavoidable arrays on one or two symbols.

References

[1] N. J. Cavenagh, Avoidable partial latin squares of order 4m + 1, Ars Combinatoria, 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 Annals of Combinatorics.

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

[4] J. Cutler, L–D. Öhman, Latin squares with forbidden entries, Electronic Journal of Combinatorics 13(1) (2006) R47.

[5] B. Farzad, M. Molloy and B. Reed, (Δ − k)-critical graphs. Journal of Combinatorial Theory, Series B 93 no. 2 (2005) 173–185.

[6] F. Galvin, The list chromatic index of a bipartite multigraph. Journal of Combinatorial Theory, Series B 63 (1995) 153–158.

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

[8] A. J. W. Hilton, C. A. Rodger, Latin squares with prescribed diagonals, Can. J. Math. 34 no. 6 (1982), 1251–1254.

[9] B. McKay, Practical Graph Isomorphism, Congressus Numerantium, 30 (1981) 45–87.

[10] A. Schrijver, Combinatorial optimization, Springer Verlag, Berlin (2003).

[11] W. T. Tutte, The factors of graphs, Can. J. Math. 4 (1952) 314–328.

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