EXTENDING PARTIAL LATIN CUBES

TRISTAN DENLEY AND LARS-DANIEL ÖHMAN

Abstract. In the spirit of Ryser’s theorem, we prove sufficient conditions on k, ℓ and m so that k × ℓ × m Latin boxes, i.e. partial Latin cubes whose filled cells form a k × ℓ × m rectangular box, can be extended to a k × n × m latin box, and also to a k × n × n latin box, where n is the number of symbols used, and likewise the order of the Latin cube.

We also prove a partial Evans type result for Latin cubes, namely that any partial Latin cube of order n with at most n − 1 filled cells is completable, given certain conditions on the spatial distribution of the filled cells.

1. Introduction

Four central theorems in the theory of Latin squares are Hall’s theorem on distinct representatives, as applied to the extension of Latin rectangles to Latin squares [5], Ryser’s theorem [10], Smetaniuk’s theorem [11] and Evans’ theorem on finite embeddability [4].

For higher dimensional Latin structures, Cruse [2] has shown that any finite partial Latin hypercube can be embedded in a finite Latin hypercube, which is an analogue of Evans’ theorem for arbitrary dimension, but the bound that he obtains on the size of the Latin hypercube to embed in is probably not best possible. We note that the main difference between embedding and extending partial Latin structures, is that when embedding, the partial stucture contains a given set of symbols, and the structure to embed in introduces a (great) number of new symbols. In contrast to this, extending presupposes that all active symbols may already be present in the partial structure, and no new symbols are introduced in the extension.

For the three other theorems, no corresponding generalisations to higher dimensions are known. In fact, some natural generalisations of the aforementioned theorems do not hold. For example, a k×n×n partial Latin cube may not be completable to a full Latin cube. When k = n − 1, completion is always possible, as can easily be seen, but Kochol [7] produced examples of incompletable k × n × n partial Latin cubes (PLC:s) for \frac{n}{2} < k ≤ n − 2. Kochol also conjectured that any (\frac{n}{2} − 1) × n × n partial Latin cube is completable.

However, McKay and Wanless [9] have given examples of a 2 × 5 × 5 and a 2 × 6 × 6 incompletable partial Latin cube, thus disproving Kochol’s conjecture. In general, therefore, there is no hope of completing even a PLC consisting of two complete layers to a full Latin cube.

In the present paper we will, in the spirit of Ryser’s theorem, find conditions for when certain k × ℓ × m PLC:s, namely Latin boxes, can be extended to k × n × m Latin boxes, and subsequently, to k × n × n Latin boxes. We can thus start with a block, extend it in one dimension, and then extend in a second dimension, but we are not yet able to extend in the third dimension.

We will also investigate the analogue of Smetaniuk’s theorem in three dimensions, obtaining partial results.

2. Ryser’s theorem revisited

In what follows, we shall make use of the simple fact that a balanced bipartite graph B on 2n vertices has a complete matching if δ(B) ≥ \frac{n}{2}, and, in general, a t-factor if δ(B) ≥ \frac{n}{2} + t − 1, where δ(B) is the minimum degree of B.

A Latin cube of order n is a 3-dimensional n × n × n array on the symbols [n], such that each symbol occurs exactly once in each 1-dimensional subarray. We shall call a 1-dimensional subarray where only the first coordinate changes a fiber, changing only the second coordinate gives us a row, and the third coordinate a column. Keeping the first coordinate fixed gives us a layer, where we will speak of layers with higher indices as being above layers with lower indices. Fixing the second coordinate gives a slice. A layer thus contains rows and columns and a slice contains columns and fibers.

A k × ℓ × m partial Latin cube is a k × ℓ × m array on the symbols [n] that satisfies the condition that each symbol be used at most once in each fiber, row and column. A partial Latin cube may thus have empty cells. A k × ℓ × m Latin box is a k × ℓ × m partial Latin cube where all cells are filled. The set of symbols used is [n] unless stated otherwise.

Lemma 2.1. Let A be a k × ℓ × m Latin box. If m + 2ℓ + 2k − 4 ≤ n, then A can be completed to a k × ℓ × n Latin box.

Proof. A consists of kℓ columns of length m, in k layers. Let C_{i,j} be the j:th column in the i:th layer. Let the corresponding symbols used in these columns be σ_{i,j}.

We form for each C_{i,j} a bipartite graph G_{i,j} with symbols [n] \ σ_{i,j} on one side and rows m + 1, …, n on the other side of the bipartition, where an edge (r, s) is present if symbol s can be placed in row r without creating a conflict. We complete columns C_{1,1}, C_{1,2}, …, C_{1,ℓ}, C_{2,1}, …, C_{k,ℓ} in this order. Completing column C_{i,j} is equivalent to finding a complete matching in G_{i,j}. It holds that δ(G_{i,j}) ≥ n − m − (i − 1) − (j − 1), since we have to take into account the symbols used in C_{1,j}, …, C_{i−1,j} and C_{i,1}, …, C_{i,j−1}. Since i ≤ k, j ≤ ℓ and m + 2ℓ + 2k − 4 ≤ n, it holds that δ(G_{i}) ≥ \frac{n−m}{2}, so we can find a matching in G_{i,j}, and thus complete column C_{i,j} without conflicts with C_{1,j}, …, C_{i−1,j} and C_{i,1}, …, C_{i,j−1}. □

Corollary 2.2. Let A be a 2 × 2 × m Latin box. If m ≤ n − 4, then A can be extended to a 2 × 2 × n Latin box.

Proof. Set k = 2, ℓ = 2 in Lemma 2.1. □

If m = n − 1 the corollary doesn’t hold, and likewise, if m = n − 2, the corollary also doesn’t hold. A concrete example of the second fact is if [n]\σ_{1,1} = {1, 2}, [n]\σ_{1,2} = {1, 3}, [n]\σ_{2,1} = {1, 2} and [n]\σ_{2,2} = {2, 3}, where σ_{i,j} is the set of symbols used in the column in the i:th layer, j:th slice. Note that the Ryser condition is satisfied in every 2-dimensional substructure.

If m = n − 3, the statement of the corollary does not follow from Lemma 2.1, but is in fact true, which can be verified by a rather short case analysis. In general, Lemma 2.1 is therefore not best possible.

Before we look at when a k × n × m Latin box extends to a k × n × n Latin box, we give an if-and-only-if condition on when a k × n × (n − 1) Latin box extends to a k × n × n Latin box, in Proposition 2.3, and before we go for full generality, we prove in Theorem 2.4 the special case k = 2, m = 2, in the hope that the proof idea will be more transparent.

Proposition 2.3. A k × (n − 1) × n Latin box is extendable to a k × n × n Latin box iff for each set of rows with shared third coordinate each symbol is used at least k − 1 times.

Proof. Observe that each row in each of the k layers has n − 1 symbols out of n, so the only possible sizes of their pairwise overlap are n − 1 and n − 2.

If in any two rows with the same first or third coordinate this overlap is n−1, one and the same symbol would be forced in the last cell of these two rows, creating a conflict. For rows in the same layer (i.e. with the same first coordinate), this is impossible, since this would imply that some symbol is used strictly less than n−1 times in that layer, but there are n(n−1) filled cells in each layer, and thus each symbol must be used exactly n − 1 times in each layer.

If for some third coordinate s two rows sharing this coordinate have overlap n − 1, one and the same symbol is absent from these two rows, and thus used at most k − 2 times in the set of rows with third coordinate s, proving the necessity of the condition.

To prove sufficiency, observe that if the condition holds, each single row can be completed in a unique way, without conflict between columns sharing their third coordinate since each symbol is missing from at most one such row. Thus, there will be no conflicts between rows in different layers. Also, because each layer by itself is completable in a unique way (since they are all partial (n − 1) × n Latin rectangles), there will be no conflicts within any of the layers. □

Theorem 2.4. For n ≥ 14, any 2 × n × 2 Latin box can be completed to a 2 × n × n Latin box.

Proof. Let π_{i,j} be the permutation of [n] that defines the j:th row in the i:th layer for i, j ∈ {1, 2}. We shall seek to find a derangement d such that d(π_{2,1}(s)) ≠ π_{1,1}(s), d(π_{2,1}(s)) ≠ π_{1,2}(s), d(π_{2,2}(s)) ≠ π_{1,1}(s) and d(π_{2,2}(s)) ≠ π_{1,2}(s) for all symbols 1 ≤ s ≤ n. We will impose some further restrictions on d, but for now, let’s suppose we’ve found such a d.

We now complete the bottom layer up until the (n − 2):th row. In doing so, however, we will also see to it that we avoid conflicts with d ∘ π_{2,1} and d ∘ π_{2,2}. For example, in the first column, we will of course have to avoid using symbols π_{1,1}(1) and π_{1,2}(1), but we will also avoid symbols d(π_{2,1}(1)) and d(π_{2,2}(1)). With these extra restrictions, since d(π_{2,1}(s)) ≠ π_{1,1}(s), d(π_{2,1}(s)) ≠ π_{1,2}(s), d(π_{2,2}(s)) ≠ π_{1,1}(s) and d(π_{2,2}(s)) ≠ π_{1,2}(s), we can complete the bottom layer except the last two rows, by Hall’s theorem.

The symbols not yet used in the remaining two cells of the s:th column of the bottom layer are d(π_{2,1}(s)) and d(π_{2,2}(s)).

To complete the second layer, we place in row 3 ≤ j ≤ n−2 the permutation d^{−1} ∘ π_{1,j}. Since d, and hence d^{−1} is a derangement, the two layers will not conflict, and since d(π_{2,1}(s)) ≠ π_{1,j}(s) and d(π_{2,2}(s)) ≠ π_{1,j}(s) for all 3 ≤ j ≤ n − 2 and all s, it also holds that d^{−1} ∘ π_{1,j} will not conflict with π_{2,1} and π_{2,2}.

The symbols not yet used in the remaining two cells of the s:th column of the top layer are d^{−1}(π_{1,1}(s)) and d^{−1}(π_{1,2}(s)).

One way (which we shall stick to) of completing the last two rows in the bottom and top layer is by setting π_{1,n−1} = d ∘ π_{2,1} and π_{1,n} = d ∘ π_{2,2} in the bottom layer, and π_{2,n−1} = d^{−1} ∘ π_{1,1} and π_{2,n} = d^{−1} ∘ π_{1,2} in the top layer. This means that we have to impose two further restrictions on d, namely that d(π_{2,1}(s)) ≠ d^{−1}(π_{1,1}(s)) and d(π_{2,2}(s)) ≠ d^{−1}(π_{1,2}(s)).

To summarize, we need a derangement d that satisfies the following inequalities for each index s:

\begin{matrix}d(π_{2,1}(s)) & ≠ & π_{1,1}(s) \\ d(π_{2,1}(s)) & ≠ & π_{1,2}(s) \\ d(π_{2,2}(s)) & ≠ & π_{1,1}(s) \\ d(π_{2,2}(s)) & ≠ & π_{1,2}(s) \end{matrix}

\begin{matrix}d(π_{2,1}(s)) & ≠ & d^{−1}(π_{1,1}(s)) \\ d(π_{2,2}(s)) & ≠ & d^{−1}(π_{1,2}(s)) \end{matrix}

Finding d is equivalent to finding a matching in the complete bipartite graph K_{n,n} with a number of edges removed. First of all, we must remove edges (i, i), since d must be a derangement. Next, each of the inequalities above effectively specifies a matching in K_{n,n} that has to be removed. In total, we remove 7 matchings, that are not necessarily disjoint, from K_{n,n}, yielding a graph G with minimum degree at least n − 7, so if n ≥ 14 the minimum degree is at least \frac{n}{2} and we can find such a d. □

Generalizing Theorem 2.4 to extending a k×n×m Latin box, for general k and m, will work in a similar way, but we shall need k − 1 derangements, which we will select sequentially.

Theorem 2.5. For n ≥ 2(m^{2}(k − 1) + m(k − 1)^{2} + 1), any k × n × m Latin box can be extended to a k × n × n Latin box.

Proof. Let π_{i,j} be the permutation in the j:th row in the i:th layer. We shall seek to find a set of derangements d_{i}, 2 ≤ i ≤ k such that d_{i}(π_{i,j_{1}}(s)) ≠ π_{1,j_{2}}(s) and in general d_{i_{1}}(π_{i_{1},j_{1}}(s)) ≠ d_{i_{2}}(π_{i_{2},j_{2}}(s)) for all i_{1} ≠ i_{2}, 1 ≤ j_{1}, j_{2} ≤ m and for all s. These conditions imply in particular that the derangements are mutual derangements.

Again, we will impose some further restrictions on the d_{i}, but for now, let’s suppose we’ve found such a set of d_{i}.

We now complete the bottom layer up until the (n − (k − 1)m):th row. In doing so, however, we will also see to it that we avoid conflicts with d_{i} ∘ π_{i,j} for all 2 ≤ i ≤ k, 1 ≤ j ≤ m. By Hall’s theorem, this is possible.

To complete the first n − (k − 1)m rows of the i:th layer, we place the permutation d_{i}^{−1} ∘ π_{1,j} in row m + 1 ≤ j ≤ n − (k − 1)m. Since d_{i} is a derangement, layers 1 and i will not conflict, and since d_{i}(π_{i,j_{1}}(s)) ≠ π_{1,j_{2}}(s) for all 1 ≤ j_{1}, j_{2} ≤ m and all s, there will be no conflicts within the i:th layer. Also, since d_{i_{1}}(s) ≠ d_{i_{2}}(s) for all s, there will be no conflict between layers i_{1} and i_{2}.

The symbols not yet used in the remaining (k − 1)m cells of the s:th column of the first layer are d_{i}(π_{i,j}(s)) for 2 ≤ i ≤ k, 1 ≤ j ≤ m. We can therefore complete the last (k − 1)m rows in layer 1 without conflict by setting π_{1,n−(k−1)m+(i−2)m+j} = d_{i} ∘ π_{i,j} for 2 ≤ i ≤ k, 1 ≤ j ≤ m.

Let I_{i} = {2, 3, …, k} \ {i}, and f_{i}(·) be the function that maps the i_{1}:th index in I_{i} to the number i_{1}. In the s:th column of the i:th layer, 2 ≤ i, the symbols not yet used in the last (k − 1)m rows are d_{i}^{−1}(π_{1,j}(s)) for 1 ≤ j ≤ k and d_{i}^{−1}(π_{1,n−(k−1)m+(i_{1}−2)m+j}(s)) for i_{1} ∈ I_{i}, which translates to d_{i}^{−1}(d_{i_{1}}(π_{i_{1},j}(s))) for i_{1} ∈ I_{i}, 1 ≤ j ≤ k.

To complete these last rows, we choose to set π_{i,n−(k−1)m+j} = d_{i}^{−1} ∘π_{1,j}, and π_{i,n−(k−1)m+(f_{i}(i_{1}))m+j} = d_{i}^{−1}(d_{i_{1}}(π_{1,n−(k−1)m+(i_{1})m+j})), for i_{1} ∈ I_{i}, 1 ≤ j ≤ m. For an illustration of this, see Example 2.6.

This ensures that there are no conflicts within layer i, but also means that we have to impose a number of further restrictions on the d_{i}, to avoid conflicts in fibers. For notational convenience, we set d_{1} = id. To summarize, we need a set of k − 1 derangements {d_{i}}_{i=2}^{i=k} that satisfy the following two sets of inequalities. The first set ensures that rows (m + 1), …, (n − (k − 1)m) are completable, and the second set of inequalities ensures that there are no conflicts within fibers intersecting the last (k − 1)m rows.

d_{i_{1}}(π_{i_{1},j_{1}}(s)) ≠ d_{i_{2}}(π_{i_{2},j_{2}}(s)) for i_{1} ≠ i_{2}, 1 ≤ j_{1}, j_{2} ≤ m, all s

For the second set of inequalities, for each 1 ≤ i ≤ k−1, each 1 ≤ j ≤ m, the following sets of permutations are required to be mutual derangements.

d_{k}^{−1} ∘ d_{i} ∘ π_{i,j} d_{k−1}^{−1} ∘ d_{i} ∘ π_{i,j} … d_{i+1}^{−1} ∘ d_{i} ∘ π_{i,j} d_{i}^{−1} ∘ d_{i+1} ∘ π_{i+1,j} d_{i−1}^{−1} ∘ d_{i+1} ∘ π_{i+1,j} … d_{1}^{−1} ∘ d_{i+1} ∘ π_{i+1,j}

We find the d_{i} in the natural order, starting with i = 2. For each d_{i}, we take into account only the inequalities involving indices i and lower. Each successfully found d_{i} then restricts the choice of the subsequent derangements. Choosing d_{i} is equivalent to finding a perfect matching in a bipartite graph G_{i} ⊂ K_{n,n}. G_{i} is formed by removing m^{2}(i − 1) + m(i − 1)^{2} + 1 matchings from K_{n,n}. There are m^{2}(i − 1) conditions of the first type on d_{i}, and m(i−1)^{2} conditions of the second type, and finally the 1 is because d_{1} = id, so all the d_{i} have to be derangements for i ≥ 2. Thus, selecting d_{k} is the hardest, and this is possible if n ≥ 2(m^{2}(k − 1) + m(k − 1)^{2} + 1). □

Example 2.6. In Theorem 2.5, if we set k = 3, m = 2, the last 4 rows will be as in Figure 1. Note that d_{1} = d_{1}^{−1} = id.

\begin{matrix}d_{3}^{−1} ∘ d_{1} ∘ π_{1,1} & d_{3}^{−1} ∘ d_{1} ∘ π_{1,2} & d_{3}^{−1} ∘ d_{2} ∘ π_{2,1} & d_{3}^{−1} ∘ d_{2} ∘ π_{2,2} \\ d_{2}^{−1} ∘ d_{1} ∘ π_{1,1} & d_{2}^{−1} ∘ d_{1} ∘ π_{1,2} & d_{2}^{−1} ∘ d_{3} ∘ π_{3,1} & d_{2}^{−1} ∘ d_{3} ∘ π_{3,2} \\ d_{1}^{−1} ∘ d_{2} ∘ π_{2,1} & d_{1}^{−1} ∘ d_{2} ∘ π_{2,2} & d_{1}^{−1} ∘ d_{3} ∘ π_{3,1} & d_{1}^{−1} ∘ d_{3} ∘ π_{3,2} \end{matrix}

Figure 1. How to complete the last 4 rows when extending a 3 × n × 2 Latin box to a 3 × n × n Latin box

It is testimony to our limited knowledge of hypergraph matchings that the above results all go to great lengths to reduce problems most naturally stated as hypergraph problems to bipartite matching problems. Obtaining something like a generalization of Hall’s theorem to r-partite r-uniform hypergraphs would be a great contribution to this area of research.

3. A multi-dimensional Evans’ conjecture

Any partial Latin square with at most n − 1 entries is completable, as conjectured by Evans, and proven by Smetaniuk. The most natural generalization of this would be the following conjecture.

Conjecture 3.1. Let P be a partial r-dimensional Latin hypercube of order n. Suppose that P has at most n − 1 entries. Then P is completable.

Since the proportion of filled cells dwindles rapidly as the number of dimensions increases, it would seem most reasonable that the conjecture is, in fact, true. One might even think that we could allow more than n − 1 entries in P, provided of course that no more than n − 1 of them occur in any 2-dimensional substructure, but as the example in Figure 2 shows, n − 1 is really best possible. Furthermore, the example easily generalizes to any order and any dimension.

1 1 1 1  1

Figure 2. The first two layers of an incompletable partial Latin cube with n entries

Smetaniuk’s proof for the 2-dimensional case cannot be used for higher dimensions, and one major hurdle is the lack of knowledge about the structure of Latin cubes. The following lemma essentially only specifies a situation when a partial Latin cube can be embedded in a cyclic Latin cube, but obviously, there are many partial Latin cubes that are not this wellbehaved.

Lemma 3.2. Let P be a partial Latin cube of order n. Suppose there exists a cyclic permutation σ of the symbols 1, …, n such that the partial Latin square P^{∗} obtained by superimposing σ^{k−1}(l_{k}) for 1 ≤ k ≤ n where l_{k} is the k:th layer of P, is completable. Then P is completable.

Proof. Observe that P^{∗} coincides with all the entries already present in the bottom layer, and there are no conflicts between P^{∗} and any symbols already present in higher layers, since σ is cyclic. We can therefore let P^{∗} be the bottom layer. Further, for k ≥ 1 let layer k be given by σ^{−k+1}(P^{∗}).

Since σ is cyclic, and hence the σ^{−k+1} are mutual derangements, there will be no conflicts between layers, and σ^{−k+1}(P^{∗}) will coincide with all entries already present in layer k. □

Lemma 3.2 can be used to prove Conjecture 3.1 if we know something about the distribution of the filled cells. An example of this is given in the following corollary. Also, with appropriate modifications, the lemma can be extended to arbitrary dimension.

Corollary 3.3. Let P be a partial Latin cube with at most n − 1 entries, such that no two filled cells share any coordinate. Then P is completable.

Proof. Since no two filled cells share any coordinate, the permutation σ from Lemma 3.2 can be found quite easily. □

A special case of Lemma 3.2 is when all entries are in one layer, in which case we complete that layer, and use any cyclic permutation of the symbols to complete the cube. However, even if we only have n − 1 entries, distributed between just two parallel layers, Lemma 3.2 is not enough.

We conclude this section with a result not covered by Lemma 3.2, where the entries already present lie in the union of a layer and a slice.

Theorem 3.4. Let P be a partial Latin cube all of whose at most n − 1 entries have either first coordinate 1 or second coordinate 1. Then P is completable.

Proof. Let L_{1} be the layer with first coordinate 1, and L_{2} the slice with second coordinate 1. Further, let S = L_{1} ∩ L_{2}, the spine.

By Smetaniuk’s theorem, each L_{i} is completable separately. Suppose without loss of generality that L_{1} has fewer entries than L_{2}, and complete L_{2} arbitrarily. This of course adds entries to L_{1}, since L_{1} and L_{2} share the cells in S. We denote by L^{∗} the layer L_{1} with the additional entries in S amended. We shall prove that L^{∗} is completable, and that we subsequently can complete the whole cube.

L_{1} has at most ⌊\frac{n−1}{2}⌋ entries, so by permuting rows and columns in L^{∗}, keeping S in its place (though entries in S may be rearranged), we can fit all the entries in L_{1} \ S in a subsquare R of dimensions ⌊\frac{n−1}{2}⌋ × ⌊\frac{n−1}{2}⌋.

We can assume that R occupies the first ⌊\frac{n−1}{2}⌋ rows of L^{∗}. We form R^{∗} by amending to R the ⌊\frac{n−1}{2}⌋ entries from L^{∗} occupying the first ⌊\frac{n−1}{2}⌋ rows. We may then assume that R^{∗} fits in the first ⌊\frac{n−1}{2}⌋ + 1 columns of L_{1}. We can easily fill all the empty cells in R^{∗}, and if we try to extend this to a completion of L_{1}, we find that the condition from Ryser’s theorem demands that each symbol be used at least ⌊\frac{n−1}{2}⌋ + ⌊\frac{n−1}{2}⌋ + 1 − n ≤ 0 times, which is trivially satisfied. We still need to consider the entries in S \ R^{∗} that we added when completing L_{2}. They may not coincide with L^{∗}, but if not, we just permute rows of L^{∗} to make it so.

We have proven that the two substructures L_{2} and L_{1} can be completed one after the other. To extend this to the whole cube, suppose that the columns of the filled L_{1} are the permutations p_{1}, …, p_{k}, …, p_{n}. To fill cell (i, j, k) we use the symbol p_{k}(p_{k}^{−1}(s(i, 1, k)+j −1)), where s(i, 1, k) denotes the symbol in position (i, 1, k).

To see that the resulting structure is a Latin cube, observe that all p_{i} are mutual derangements, so there will be no conflicts in the i-dimension. Since L_{1} and L_{2} have been completed to Latin squares, there will be no conflict in the j- or k-dimensions. □

4. Concluding remarks

In the proof of Theorem 3.4 a construction of Latin cubes from a layer and a slice was used. This construction generalizes to arbitrary dimension. For example, two permutations p_{1} and p_{2} with p_{1}(1) = p_{2}(1) can be ‘composed’ to form a Latin square L = p_{1} ∘ p_{2}, by taking p_{1} to be the first row and p_{2} the first column and placing in cell (i, j) the symbol p_{2}(p_{2}^{−1}(p_{1}(j)) + i − 1), where p_{2}^{−1}(p_{1}(j)) + i − 1 is taken modulo n. The resulting Latin square will have symbols in the same cyclic order p_{2} in each column, with the starting points being given by p_{1}. Of course, the roles of p_{1} and p_{2} can be interchanged.

The Latin squares that can be constructed in this way are exactly the Latin squares that are isotopically equivalent to the basic cyclic Latin square, namely with entry i + j − 1 modulo n in cell (i, j). For Latin cubes, the corresponding construction gives more than the cyclic Latin cubes, with entry i + j + k − 2 modulo n in cell (i, j, k), but still a far cry from all Latin cubes.

We would like to pose the following problem, which seems possible to solve. We conjecture that there indeed is such an N.

Problem 1. Find an N such that n ≥ N implies that any 2 × n × n Latin box is always extendable to a Latin cube of order n.

References

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

[2] A. B. Cruse, On the finite completion of partial Latin cubes, J. Combinatorial Theory Ser. A 17 (1974) 112–119.

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

[4] T. Evans, Embedding incomplete Latin squares, Amer. Math. monthly 67 (1960) 958–961.

[5] P. Hall, On representatives of subsets, J. London Math. Soc. 10 (1935) 26–30.

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

[7] M. Kochol, Relatively narrow Latin parallelepipeds that cannot be extended to a Latin cube, Ars Comb. 40 (1995) 247–260.

[8] K. Markström & L–D. Öhman, Unavoidable arrays, manuscript.

[9] B. D. McKay & I. M. Wanless, A census of small Latin hypercubes, SIAM J. Discrete Math. 22 (2008), no. 2, 719–736.

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

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

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