The Intricacy of Avoiding Arrays

Lars–Daniel Öhman

Abstract. Let A be any n × n array on the symbols [n], with at most m symbols in each cell. An n × n Latin square L avoids A if no entry in L is present in the corresponding cell in A. If m = 1 and A is split into two arrays B and C in a special way, there are Latin squares L_{B} and L_{C} avoiding B and C respectively. In other words, the intricacy of avoiding arrays is 2, the number of arrays into which A has to be split. We also investigate the case m > 1, derive some upper and lower bounds, and propose a conjecture on the exact value of the intricacy for the general case.

1. Introduction

The concept of intricacy (for completing partial Latin squares) was introduced by Daykin and Häggkvist in [5], and a sample of applications to other problems can be found in [9].

The general concept of intricacy deals with combinatorial construction problems. Given a set of partial structures and a set of goal structures, we ask first which partial structures are extensible to some goal structure. If there are no partial structures that are not extensible, the problem is dubbed simple, and we say that the intricacy is 1. If at least all minimal (with respect to some measure) partial structures are extensible, we say that the problem at hand is fair. For unfair problems we do not define the intricacy.

The intricacy for a general combinatorial construction problem is the minimum k ∈ ℕ such that any partial structure can be partitioned into k or fewer extensible partial structures.

An array A is avoidable iff there is a Latin square L that differs from A in every cell. For the problem of finding this Latin square, the intricacy then is the natural number that answers the following question: “If we want to split an array into avoidable arrays, what is the maximum number of arrays we need to use?” In [3] it is proven that this number is at most 3.

The combinatorial construction problem of creating an n × n Latin square that avoids an array with at most m entries in each cell is certainly fair for n > m, if we say that a minimal array is an array with at most m entries in at most one cell.

If m = n, the problem is not fair, so in what follows we investigate n×n arrays, with at most m < n entries in each cell. We set I(m, n) = the intricacy of avoiding n × n Latin squares with at most m entries in each cell. Evidently, I(m, n) grows monotonely with m.

2. m = 1

The result in this section is from [12]. There are unavoidable arrays, for example any array containing a whole row or column of just one symbol, so the intricacy of avoiding arrays with at most one entry in each cell is not 1. If m = n = 1 the problem is not fair, as observed above, so we assume that n ≥ 2 to avoid this degenerate case.

Theorem 2.1. The intricacy of avoiding arrays is 2, i.e. I(1, n) = 2.

Proof. Let A be any n × n array on the symbols [n]. Split A into arrays B and C, so that C is empty. Certainly, there is a latin square L_{C} avoiding C. For each cell in B, move the entry to array C iff it differs from the corresponding entry in L_{C}. Then L_{C} will still avoid C, and the entries left in B form a partial latin square, which is completable (to L_{C}, for instance). By Theorem 2.1 in [3] B is avoidable, and is avoided by some latin square L_{B}, which in fact is L_{C} with symbols permuted without fixed points. □

This gives a positive resolution to Conjecture 3.3 in [3].

3. Upper bounds on I(m, n) for m ≥ 2

When m ≥ 2, we must decide what we mean by a partition of an array. Do we partition the sets of symbols in each cell, or do we merely partition the cells?

If we allow ourselves to partition the sets of symbols in each cell, then for any n > 1 the intricacy of avoiding arrays with m ≤ n entries is two, by the exact same argument as Theorem 2.1.

If the partition of the array keeps entries in a cell together, the situation is more difficult. We cannot mimic Theorem 2.1, for any m ≥ 2, for the cells not moved to the array C may prescribe as many as mn − n symbols that a given symbol must not be permuted to. We may even be so unfortunate that no cell can be moved to C. If we choose to proceed along the lines of this theorem, it is obvious that more care must be taken in choosing the Latin square L_{C}.

Given an n × n array A with m entries in each cell, that we wish to split into avoidable arrays, step one is to find a Latin square avoiding as many of the entries in A as possible. We proceed as follows. Take any n × n Latin square L, on the symbols [n]. For each permutation p ∈ Π_{n} of these symbols, we let p(L) be the Latin square L with symbols permuted by p. Let (i, j) be a cell in A, and p(L) ∩ A be the set of cells (i, j) where p(L) and A are in conflict, i.e. the entry in cell (i, j) of p(L) is one of the symbols in cell (i, j) of A. A standard double count gives that

∑_{p∈Π_{n}} |p(L) ∩ A| = ∑_{(i,j)∈A} |{p ∈ Π_{n} : (i, j) ∈ p(L) ∩ A}| = n^{2}m(n − 1)!

Taking averages, and remembering that |Π_{n}| = n! we see that there exists a permutation p_{1} ∈ Π such that p(L) ∩ A ≤ nm. In other words, given any Latin square L, there is a permutation of its symbols, so that it conflicts with A in at most nm cells. Note that permuting rows and columns as well does not improve on these calculations. We fix this permutation, p_{1}, and let L_{1} = p_{1}(L). We also let B_{1} = A − (L_{1} ∩ A) be the array with the entries from A not conflicting with L_{1}, so that B_{1} does not conflict with L_{1}, and no further cells from A may be moved to B_{1} without creating a conflict.

For A_{2} = A − B_{1}, the array with the remaining cells from A, we can repeat this procedure, and find a permutation p_{2} such that |p_{2}(L) ∩ A_{2}| ≤ m^{2}. We then set B_{2} = A_{2} −(L_{2} ∩A_{2}) and A_{3} = A_{2} −B_{2}. At this stage, we observe that the at most m^{2} non-empty cells in A_{3} can surely be avoided provided m^{2}m < n, since each of them contains at most m forbidden symbols. For a proof of this claim, see Proposition 3.5. Thus, if m < n^{\frac{1}{3}} we have that I(m, n) ≤ 3.

After constructing k arrays B_{i}, we get an A_{k+1} with at most \frac{m^{k}}{n^{k−2}} nonempty cells. If m times this number is less than n, A_{k+1} is avoidable, and we may take it as our B_{k+1}. Thus we have the following proposition.

Proposition 3.1. If m < n^{\frac{k−1}{k+1}} , then I(m, n) ≤ k + 1.

We can do slightly better than this by considering pairs of Latin squares that do not overlap in any cells, and permutations of their symbols by one and the same permutation.

Proposition 3.2. If m^{3} − m^{2} < n − 1, then I(m, n) ≤ 3.

Proof. Given any n × n array A with at most m entries in each cell, we choose any pair of Latin squares L and L̂ with |L ∩ L̂| = 0, the number of cells where L and L̂ have the same entries. For any permutation p of the symbols, we also have |p(L) ∩ p(L̂)| = 0. We have, using the same double count as before, the following.

∑_{p∈Π_{n}} |p(L) ∩ p(L̂) ∩ A| = ∑_{(i,j)∈A} |{p ∈ Π_{n} : (i, j) ∈ p(L) ∩ p(L̂) ∩ A}|
= n^{2}m(m − 1)(n − 2)!

Taking averages over Π_{n}, we find a permutation p_{0} with at most (m^{2} − m)n/(n−1) bad cells. If m times this number is less than n, i.e. m^{3}−m^{2} < n − 1, we have I(m, n) ≤ 3. □

The upper bound n^{2} for I(m, n) is trivial, as the problem is fair, and it can be shown that I(m, n) is bounded from above by n for any m ≤ n−1. To do this, we need a result of G. J. Chang, cited (and again proved) in [8].

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

We will also make use of the positive solution to Evans’ conjecture by B. Smetaniuk [11].

Theorem 3.4. (Smetaniuk) Any partial n × n Latin square with at most n − 1 entries is completable.

With this theorem at hand, we may prove the following proposition, used without proof in propositions 3.1 and 3.2. Note that the proposition is sharp, for if there are n entries, they can fill a row or column with one symbol, or one cell with all n symbols, and these are unavoidable arrays.

Proposition 3.5. Let A be an n × n array, where multiple entries in each cell is allowed. If the total number of entries in A, counted with multiplicities, is at most n − 1, then A is avoidable.

Proof. Let a_{1}, a_{2}, …, a_{k} be the non-empty cells of A, with symbols L_{i} in cell a_{i}. We have k ≤ n − 1 and |L_{i}| ≤ n − k for all i. We may assume that |L_{1}| ≥ |L_{2}| ≥, …, |L_{k}|. Choose a permissible symbol b_{1} ∉ L_{1} for cell a_{1}, and forbid the use of b_{1} in any cells a_{j} that lie in the same row or column as a_{1}. Do this for each i with 1 ≤ i ≤ k. At step i, we must choose a symbol for cell a_{i}, where there are at least n − |L_{i}| − (i − 1) symbols available. Since |L_{i}| ≤ (n − 1) − ∑_{1}^{i−1} |L_{j}| the number of available symbols in cell a_{i} is at least n − (n − 1) + ∑_{1}^{i−1} |L_{j}| − (i − 1) = ∑_{1}^{i−1} |L_{j}| − i + 2 ≥ 1. When we are finished, the chosen b_{i} are a partial Latin square with at most n−1 entries, that is completable by Theorem 3.4. The completed Latin square certainly avoids A. □

If we prescribe that no cell of A may contain more than n − 1 symbols, we se that there is essentially only one counterexample to the above proposition, with at most n entries in A in total, namely one row or column filled with one and the same symbol.

Proposition 3.6. Let 1 ≤ m ≤ n − 1, and let A be an n × n array with at most m entries in each cell. If the total number of non-empty cells in A is at most n − m then A is avoidable.

Proof. There is no one full row of just one symbol, because 1 ≤ m. If we can avoid the non-empty cells then Theorem 3.4 ensures that the partial array found in this way can be completed to a full Latin square. Choose, in arbitrary order, for each non-empty cell a permitted symbol, and forbid its use in any other non-empty cell in the same row or column. Each nonempty cell allows at least n − m different symbols, and there are n − m of them, so the process will not break down. □

With these results, we can also improve on Proposition 3.2.

Theorem 3.7. Let (m^{2}−m)n/(n−1) ≤ \frac{n}{2} +1 and n ≥ 4. Then I(m, n) ≤ 3.

Proof. Let A be the array, with at most two entries in each cell, that is to be avoided. By the proof of Proposition 3.2 there are two orthogonal Latin squares L and L̂ such that they together avoid all but at most (m^{2} − m)n/(n − 1) cells of A. This is not quite enough to ensure that the remaining entries may be avoided. An n×n array with (m^{2}−m)n/(n−1) ≤ \frac{n}{2} + 1 non-empty cells, each containing m symbols, is avoidable. To see this, observe that for m ≥ 3 it holds that if (m^{2} − m)n/(n − 1) ≤ \frac{n}{2} + 1, then certainly m ≤ \frac{n}{2} − 1. The (m^{2} − m)n/(n − 1) cells are therefore avoidable by Proposition 3.6.

If m = 1 we have Theorem 2.1, so the remaining case to be treated is when m = 2. We then have (2^{2} − 2)n/(n − 1) < 3 non-empty cells, for n ≥ 4, each containing at most 2 symbols. This is obviously avoidable. □

Solving for m in the inequality, we get m ≤ \frac{1}{2} + \sqrt{\frac{n}{2} + \frac{3}{4} − \frac{1}{n}}, so if m and n satisfy this condition, we have I(m, n) ≤ 3.

Any array with at most n − 2 entries in each cell may be decomposed into n diagonals, so that on these diagonals the use of at most n − 2 symbols is forbidden in each cell. Obviously, for each such part we can construct partial Latin squares (diagonals) that avoid the n − 2 symbols in the relevant cells, and that do not use one symbol exactly n − 1 times. By Theorem 3.3, each such array is completable, and thus for m ≤ n − 2 we have I(m, n) ≤ n.

From now on, we term a generalized diagonal with exactly n−1 identical sets of n−1 symbols a bad diagonal. If we could decompose an n×n array A with at most n − 1 symbols in each cell into diagonals, none of which is bad, we would have established that I(n − 1, n) ≤ n, by Theorem 3.3. However, it is easy to find examples of arrays where this is not possible. We must therefore investigate this case more carefully.

Theorem 3.8. I(n − 1, n) ≤ n.

Proof. Partition A into the n diagonals parallel to the diagonal consisting of entries (i, i) (the main diagonal). Some of the diagonals may be bad. Let these be d_{1}, …, d_{ℓ}, and the single cells of differing type in each diagonal be c_{1}, …, c_{ℓ}. Also, we call the symbol not prohibited in n − 1 cells of d_{i} S_{i}, and the symbol not prohibited in exactly one cell σ_{i}.

If there is a set of diagonals D with S_{i} = S_{j} for any two d_{i}, d_{j} ∈ D, then σ_{i} ≠ S_{j} for all diagonals in D. We switch cells c_{i} to some other part d_{j}. After this switching, involving all the diagonals, they will all be avoidable. We may thus assume that all S_{i} are distinct.

If there is a pair of bad diagonals d_{i} and d_{j}, such that σ_{i} = S_{j} (and thus S_{i} ≠ S_{j}), we can move cell c_{i} to part d_{j}, and move from d_{j} to d_{i} the cells from d_{j} that lie in the same row or column as c_{i} (there are exactly 2 of them). Now d_{j} forces a partial Latin square with n − 1 entries, which is completable by Theorem 3.4, so d_{j} is avoidable. The diagonal d_{i} forces the entries S_{i} on almost a full diagonal, and the entries S_{j} in two cells off this diagonal. This configuration is obviously completable to a Latin square, so d_{i} is also avoidable. Thus we can get rid of any set of bad diagonals with the same symbols σ and S.

Thus we have the situation where σ_{i} ≠ S_{j} and S_{i} ≠ S_{j} for all i and j. Now if we move c_{i} to d_{i+1}, where indices are taken modulo ℓ, each resulting d_{i} will obviously be avoidable. The only problem, then, is if ℓ = 1.

We must get rid of the cell c_{1} from the single bad diagonal d_{1}. We do so by moving c_{1} to some other part, d_{k}. This may make d_{k} unavoidable, for instance if the cells in d_{k} in the same row or column as c_{1} permit only the symbol σ_{1}. If this happens, we simply move the offending cells from d_{k} to d_{1}, making d_{k} avoidable, perhaps by reducing the number of non-empty cells in d_{k} to n − 1 and applying Theorem 3.4. Also, d_{1} obviously stays avoidable. This establishes that I(n − 1, n) ≤ n. □

It turns out that we can use the following result from [9] together with Galvin’s theorem on the list chromatic index of bipartite graphs [6] to find some further upper bounds on I(m, n).

Theorem 3.9. (Opencomb) The intricacy of completing a partial Latin square is less than or equal to 4.

Proposition 3.10. For m ≤ \frac{n}{2} it holds that I(m, n) ≤ 8, and for \frac{n}{2} ≤ m ≤ n − 1 it holds that I(m, n) ≤ 4⌈\frac{n}{n−m}⌉.

Proof. When m ≤ ⌊\frac{n}{2}⌋, we split the array A we wish to avoid into two chessboard squares, A_{1} and A_{2}, where a chessboard square is all cells (i, j) with i + j odd, or the complement of this array. We observe that at least ⌈\frac{n}{2}⌉ symbols are available in each cell. Some are empty, and allow any symbol, but we disregard these cells for now. Translated into the language of list-colorings of bipartite graphs, we have to list-color the edges of a bipartite graph with maximum degree at most ⌊\frac{n}{2}⌋ and lists of length at least ⌈\frac{n}{2}⌉, so by Galvin’s theorem, there are partial Latin squares L_{1} and L_{2} avoiding A_{1} and A_{2} respectively. By Theorem 3.9, each of these can be split into 4 parts, each of which is completable. Thus, the partition induced on the A:s gives avoidable parts, and thus we have for m ≤ ⌊\frac{n}{2}⌋ that I(m, n) ≤ 8.

When m ≥ ⌊\frac{n}{2}⌋ we partition A into parts with no more than n − m empty cells in each row or column. To do this, we need not split A into more than ⌈\frac{n}{n−m}⌉ parts. Again, by Galvin’s theorem, each of these allows a partial Latin square, and by applying Theorem 3.9 we see that I(m, n) ≤ 4⌈\frac{n}{n−m}⌉. □

By using results on the completion of partial latin squares, for instance [2], specifically Corollary 11.4.2 and Theorem 11.4.11, again together with Galvin’s theorem, we can improve on Proposition 3.10. In general, results on the completion of partial Latin squares can be directly exploited in the same fashion, without much work.

Theorem 3.11. (Corollary 11.4.2 from [2]) Let P be a partial n × n latin square, all of whose entries lie within an r × s rectangle, with r + s ≤ n. Then P can be completed to an n × n latin square.

Note that for even n Theorem 3.9 follows directly from this theorem, which is a corollary of a theorem by Ryser [10]. For odd n some additional minor work is needed, but the full Theorem 3.9 is essentially a corollary to this theorem.

Theorem 3.12. (Theorem 11.4.11 from [2]) Let A be a partial 3r × 3r latin square, all of whose entries lie within two disjoint r×r squares. Then A can be completed to an n × n latin square.

This theorem can be extended in the following ways (see [13]).

Theorem 3.13. Let n = ar + t where 0 leqt, r ≤ a − 1 and let A be a partial n × n latin square, all of whose entries lie within the a − 1 first r × r squares along the main diagonal. Then A can be completed to an n × n latin square.

Theorem 3.14. Let A be a partial ar + t × ar + t latin square, all of whose entries lie within ⌈\frac{a+1}{2}⌉ disjoint r × r squares, such that each row or column only intersects one such square. Then A can be completed to an n × n latin square.

Theorems 3.11, 3.12 and 3.13 can be applied to prove the following three theorems.

Theorem 3.15. Let m ≤ \frac{n}{2}. Then I(m, n) ≤ 4.

Proof. If n is even, split the array of forbidden symbols into the four quadrants. For each of these quadrants, all non-empty cells can be avoided by Galvin’s theorem. The partial Latin squares found in this way are completable, by Theorem 3.11.

If n is odd, split the array into four \frac{n−1}{2} × \frac{n+1}{2} rectangles, properly rotated, located in the corners of the array to be avoided, such that only the cell (\frac{n+1}{2}, \frac{n+1}{2}), in the middle of the array is not covered. This cell is the fifth part. The non-empty cells in all five parts are avoidable, by Galvin’s theorem, and the partial Latin squares found in this way are completable, by Theorem 3.11.

In fact, if we look a bit closer at for example [1] or the proof of Ryser’s theorem [10] on the completability of partial Latin rectangles due to Hilton and Johnson [7] found in [2], we see that the single cell (\frac{n+1}{2}, \frac{n+1}{2}) may in fact be put in any one of the other four parts. Galvin’s theorem again ensures that this cell may be avoided, and the above references ensure that the partial Latin square found in this way is completable. □

Proposition 3.16. Let n = 3r and m ≤ \frac{2n}{3}. Then I(m, n) ≤ 5.

Proof. Let A be any n×n array with at most m entries in each cell. Since n = 3r, the array A can be divided into 9 square sectors of equal size, namely r×r. We group these sectors into 4 pairs, not choosing two sectors from the same row or column, leaving one single sector, for example the middle one, and let this be the way we split A. The nonempty cells in each part are avoidable, by Galvin’s theorem, and by Theorem 3.12, the partial Latin squares found in this way are completable. □

Theorem 3.17. Let m ≤ n+1−\sqrt{n + 1}. If \frac{n}{n−m} is an integer, I(m, n) ≤ \frac{n}{n−m} + 2. Otherwise I(m, n) ≤ ⌈\frac{n}{n−m}⌉ + 3.

Proof. Let A be the n × n array to be avoided. If \frac{n}{n−m} = a is an integer, we split A into a^{2} square sectors, with side length n − m. In the a × a square grid, consider the a diagonals parallel to the main diagonal. If we from each of these can remove at least one square, the non-empty cells in each such diagonal can be avoided, by Galvin’s theorem, and the partial Latin square found in this way can be completed by Theorem 3.13, since m ≤ n + 1 − \sqrt{n + 1} ensures that r = n − m ≥ a − 2. To remove one cell from each diagonal is easily done. Remove squares (1, a), (2, a − 1),…,(a − 1, 2) and place them in one (avoidable, by the same argument) part, and squares (1, a − 1), (2, a − 2), …,(a − 1, 1) in one (avoidable) part. We have partitioned A into \frac{n}{n−m} + 2 avoidable parts, so I(m, n) ≤ \frac{n}{n−m} + 2.

If \frac{n}{n−m} is not an integer, we may split A into as many squares of side n − m as possible, leaving a few smaller rectangles (size (n − m) × t for some suitable t) and one smaller square (size t × t) in the end. Set a = ⌈\frac{n}{n−m}⌉. We group these sectors into diagonals in the (defective) ⌈\frac{n}{n−m}⌉ × ⌈\frac{n}{n−m}⌉ grid, paralell to the main diagonal as before. Each diagonal will thus contain either a rectangle, or the t × t square. Remove from these diagonals the three parts P_{1} = {(1, a), (2, a−1), …, (a−2, 3)}, P_{2} = {(a − 1, 2), (a, 1), (2, a), (3, a − 1), …, (a − 3, 5)} and P_{3} = {(a − 2, 4), (a − 1, 3), (a, 2), (1, a − 5), (2, a − 4), …, (a − 5, 1)}. Here (i, j) signifies the square in the grid with coordinates (i, j). Each P_{i} is avoidable, using Galvin’s theorem and Theorem 3.13, and from each diagonal, we have removed two squares/rectangles, as can be easily checked, leaving an avoidable part. Thus I(m, n) ≤ ⌈\frac{n}{n−m}⌉ + 3. □

To close the gap between (n+1)−\sqrt{n + 1} and n, we prove the following.

Theorem 3.18. factor2 Let n ≤ m − 1. Then I(m, n) ≤ 2⌈\frac{n}{n−m}⌉.

Proof. Write n as n = a(n − m) + t with t < a. Split the array A into a square grid of a×a squares, with a×t rectangles along the right and bottom edges, and a t×t square in the lower left corner. Separate A into avoidable parts that each consist of half a diagonal in the grid, as in Theorem 3.17. The non-empty cells in these parts are avoidable by Galvin’s theorem, and the partial Latin squares thus found are completable, by Theorem 3.14. □

4. Lower bounds on I(m, n) when m ≥ 2

Not much is known about avoidable arrays with multiple entries. The first result in this vein known to the present author is [4]. It is obvious, however, that any family of avoidable arrays must place some additional restraints on the occurences of symbols. The examples given below are certainly in violation of some reasonable constraints.

To bound the intricacy from below, we need to find some nasty arrays that are unavoidable, unless partitioned into many parts.

Proposition 4.1. If m > \frac{n}{2} then I(m, n) ≥ 3.

Proposition 4.2. If m = n − 1, then I(m, n) ≥ n.

The example that proves both propositions is an n × n array A with entries 1, 2, …, m in each cell in the first column.

If m > \frac{n}{2} and we partition these cells into two parts, one of the parts is bound to get at least \frac{n}{2} of the cells, effectively blocking the use of symbols 1, … m in a number of cells in the first column, so that these symbols can only be used in strictly less than m cells, which is impossible. Therefore, the intricacy is not 2, and hence at least 3.

If m = n − 1, and we partition A into n − 1 parts, the pigeonhole principle gives that at least one of the parts, say B, contains at least 2 of the cells from the first column. Again, this means that m = n−1 symbols must be used in the at most n − 2 free cells in the first column of B, a contradiction.

Using the pigeonhole principle, we get a whole range of intermediate results of these two propositions.

Theorem 4.3. I(m, n) ≥ ⌈\frac{n}{n−m}⌉.

The proof consists of the same example as for the above propositions and application of the pigeonhole principle.

5. Concluding remarks

To sum up, we have that I(1, n) = 2, I(n − 1, n) = n and the following, where 2 ≤ m and ⌈\frac{n}{n−m}⌉ ≤ I(m, n) ≤ n always. In particular, for n = 2, 3 the intricacy is completely characterised.

\begin{matrix}m & I(m, n) \\ m ≤ \frac{1}{2} + \sqrt{\frac{n}{2} + \frac{3}{4} − \frac{1}{n}} & I(m, n) ≤ 3 \\ m ≤ \frac{n}{2} & I(m, n) ≤ 4 \\ m ≤ \frac{2n}{3}, n = 3r & I(m, n) ≤ 5 \\ m ≤ n + 1 − \sqrt{n + 1}, \frac{n}{n−m} ∈ ℕ & I(m, n) ≤ ⌈\frac{n}{n−m}⌉ + 2 \\ m ≤ n + 1 − \sqrt{n + 1} & I(m, n) ≤ ⌈\frac{n}{n−m}⌉ + 3 \\ m ≤ n − 1 & I(m, n) ≤ 2⌈\frac{n}{n−m}⌉ \end{matrix}

Based on this admittedly scant evidence, it seems reasonable to propose the following conjecture.

Conjecture 5.1. I(m, n) = ⌈\frac{n}{n−m}⌉ for all 1 ≤ m ≤ n − 1.

Another nice way of rewriting this conjecture is the following. If it holds that m ≤ \frac{kn}{k+1}, then I(m, n) ≤ k + 1. The specific instance I(2, 4) = 2 should be tractable by computer.

References

[1] L. D. Andersen, R. Häggkvist, A. J. W. Hilton, W. B. Poucher, Embedding incomplete Latin squares in Latin squares whose diagonal is almost completely prescribed, Europ. J. Combin. 1 (1980), pp. 5–7.

[2] A. Asratian, T. Denley, R. Häggkvist, Bipartite graphs and their applications, Cambridge university press (1998).

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

[4] J. Cutler, L–D. Öhman, Latin squares with forbidden entries, Research Report 5 (2004), Dept. of Mathematics, Umeå University.

[5] D. E. Daykin, R. Häggkvist, Problem 6347, Amer. Math. Monthly 88 (1981) p. 446.

[6] F. Galvin, The list chromatic index of a bipartite multigraph, J. Combin. Theory, Ser. B 63 (1995), pp. 153–158.

[7] A. J. W. Hilton, P. Johnson, A variation of Ryser’s theorem and a necessary condition for the list-colouring problem, in Graph colourings, Pitman Research Notes in Mathematics Series 218, Eds. R. Nelson and R. J. Wilson, Longman Scientific and Technical (1990), pp. 135–143.

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

[9] W. E. Opencomb, On the intricacy of combinatorial construction problems, Discrete Math. 50 (1984), pp. 71–97.

[10] H. J. Ryser, A combinatorial theorem with an application to Latin rectangles, Proc. Amer. Math. Soc. 2 (1951), pp. 550–552.

[11] B. Smetaniuk, A new construction on Latin squares — I: A proof of the Evans conjecture Ars Comb. 11 (1981), pp. 155–172.

[12] L–D. Öhman, The intricacy of avoiding arrays is 2, Discrete Math., 306 (2006) 531–532.

[13] L–D. Öhman, A note on completing Latin squares, manuscript, 2005.

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

Department of Mathematics and Mathematical Statistics, Umeå University, SE-901 87 Umeå, Sweden