Partial latin squares and partial transversals

The kinds of partial latin square which we discuss in this chapter are latin rectangles, row latin squares and various kinds of incomplete latin square.

3.1 Latin rectangles and row latin squares

A latin rectangle of r rows and n ≥ r columns is an r × n array of n symbols such that each row contains all the symbols and no column contains any symbol more than once. Any latin rectangle can be extended to a latin square, as we show in Theorem 3.1.1 below. The number of ways in which this can be done is discussed in Chapter 4.

Our first two theorems both make use of Hall’s theorem on representatives of subsets, namely: The necessary and sufficient condition that a system of distinct representatives, one for each member of a set {T ₁, T ₂, …, T_m } of subsets of a given set S, can be chosen simultaneously is that, for each k = 1, 2, …, m, any selection of k of the subsets shall contain between them at least k distinct elements of S. [See P.Hall(1935) for the proof.]

Theorem 3.1.1

Every r × n latin rectangle can be extended to a latin square of order n.

Proof

Let R be a r × n latin rectangle. For each j = 1, 2, …, n let us form a set S_j consisting of those n − r symbols which occur in R but which do not occur in the j-th column of R. Since each symbol occurs once in each of the r rows of R and no symbol occurs twice in any column, each symbol must occur exactly n − r times among the S_j .

Any selection of k of the S_j will contain k(n − r) occurrences of symbols and these must involve at least k distinct symbols since each symbol occurs n − r times among the S_j . Thus, the requirements of Hall’s theorem are satisfied and distinct representatives a ₁, a ₂, …, a_n can be chosen so that a_j ∈ S_j . By definition of the sets S_j , these n distinct representatives may be used to form an (r + 1)-th row of R by placing a_j in column j for j = 1, 2, …, n, and thereby yield an (r + 1) × n latin rectangle.

By repetition of the process n − r times, we eventually obtain an n × n latin square. □

The above theorem will be found in M.Hall(1945). The following extension of it is due to Ryser(1951).

Theorem 3.1.2

An r × c rectangular matrix M can be extended to a latin square based on a set ∑ of n symbols if and only if M contains no symbols other than those in ∑, no symbol appears twice in any row or column of M and the number N(i) of times that any symbol i ∈ ∑ appears in M is at least r + c − n.

Proof

The necessity of the conditions is easy to see. If we want to extend M to an r × n latin rectangle then we shall have, in the latter, r occurrences of every symbol. But in the additional n − c columns we cannot include any symbol more than n − c times, and so it must already appear r − (n − c) times in M.

As regards the sufficiency, each of the proofs known to the present authors requires a preceding lemma. [The proof of sufficiency given in the first edition of this book was incorrect because the induction step was not valid.] The original proof given by Ryser(1951), used a lemma concerning matrices of zeros and ones. In the proof given by Lindner on page 222 of [DK2], the lemma used is an extended form of P. Hall’s theorem on distinct representatives of subsets.

Here we give a proof which uses graphical ideas. The lemma which we use concerns edge-colouring of a bipartite graph. It was originally proved with the aid of P. Hall’s theorem on distinct representatives of subsets. [See, for example, page 94 of Berge(1962).] However, the elementary proof which we give here is due to Hilton(1977). The proof of the theorem itself which we give can be found on page 95 of Berge’s book but may date from earlier than this.

Lemma

If G is a bipartite graph whose maximum degree 1 is Δ, then G can be edge-coloured ² with Δ colours.

Proof

We suppose that the two vertex sets of the bipartite graph G are U = {u ₁, u ₂, …, u_r } and V = {υ ₁, υ ₂, …, υ_s }.

We colour the edges one by one until we reach an edge for which no suitable colour is available. Suppose that [u_i , υ_j ] is such an edge. Since at most Δ − 1 of the Δ (or less) edges which are incident at u_i have been coloured, there exists at least one colour α which has not been used to colour any edge incident with υ_i . Likewise, there exists at least one colour β which has not been used to colour any edge incident with υ_j . If β = α or if β has not been used to colour any edge incident with u_i , there is nothing to prove because this colour is then available to colour the edge [u_i , υ_j ]. In the contrary case, there exists a chain of one or more edges [u_i , υ_h ], [υ_h , u_k ], [u_k , υ_l ], …, which are alternately coloured β, α, β, α, β, …. This chain cannot pass through υ_j since, if so, an edge ending at υ_j would have colour β, in contradiction to our choice of β. Nor can it return to u_i , by our choice of α. Consequently, we can re-colour the edges of this chain using α, β, α, β, α, …, in place of β, α, β, α, β, …. Then edge [u_i , υ_j ] can be coloured with β.

By repetition of this process a sufficient number of times, we obtain a complete edge-colouring of G. □

We can now prove the sufficiency part of Theorem 3.1.2. Let ρ ₁, ρ ₂, …, ρ_r denote the rows of M and let σ ₁, σ ₂, …, σ_n denote the n symbols. We form a bipartite graph G whose vertex sets are {ρ ₁, ρ ₂, …, ρ_r } and {σ ₁, σ ₂, …, σ_n }. We join vertex ρ_i to vertex σ_j if and only if the symbol σ_j does not occur in row ρ_i of M.

Since exactly c symbols occur in each row of M, each vertex ρ_i of G has degree n − c. Since the symbol σ_j occurs N(j) times in M, it does not occur in r − N(j) of the rows of M. Therefore, the degree of the vertex σ_j in G is r − N(j) ≤ n − c, because −N(j) ≤ n − r − c. It follows that each vertex of the graph G has degree at most n − c. Consequently, G can be edge-coloured with at most n − c colours k ₁, k ₂, …, k_n _−c. We may use these colours to represent the n − c columns which must be adjoined to M to form an r × n latin rectangle. If the edge joining vertex ρ_i to vertex σ_j of G has colour k_s , then we put the symbol σ_j in the ρ_i -th row of column k_s . Hence, we can extend M to an r × n latin rectangle. This in turn can be extended to a latin square by Theorem 3.1.1. □

Note that Theorem 1.6.3 is an immediate corollary of Theorem 3.1.2. From Theorem 3.1.2, one can also deduce that an incomplete latin square of order t ≥ 4 with n different elements (that is, a square of order t such that a subset of its t ² cells are occupied by elements of {1, 2, …, n} and no element occurs twice in the same row or column) can be embedded in a latin square of order n provided that n ≥ 2t. This result can be found in T.Evans(1960) and again in Dénes and Pásztor(1963) where the proof is formulated in terms of the transversals of a latin square (cf. Theorem 1.6.3).

A result in a similar spirit to that of Evans was proved by Treash(1971), who showed that any finite incomplete loop which is also totally symmetric can be embedded in a finite complete totally symmetric loop. The definition of an incomplete loop is given in Section 3.4, where a number of further results concerning the embedding of incomplete latin squares and quasigroups will be found.

A modification of Theorem 3.1.2 obtained by Hilton and Johnson(1988) replaces the requirement that the number N(i) of times that any symbol i ∈ ∑ appears in M is at least r + c − n by the requirement that ∑ i = 1 n t E ( i ) = n 2 − rs si1_e , where t_E (i) is the largest size of any i-transversal outside M, defined as follows: Let L be an n × n matrix which contains the given r × c rectangular matrix M in its top left corner and such that the cells of E = L − M are all empty. For each symbol i, an i-transversal outside M is a set S of cells of E such that no two cells of S are in the same row or column and no cell of S is in the same row or column as any cell of M which contains i. For the proof of this result, see Hilton and Johnson’s paper.³

In Section 2.6 we defined the concepts of row complete and complete latin square. Analogously, an r × n latin rectangle, r ≤ n/2, is said to be row complete if the unordered pairs of adjacent elements appearing in its rows are all distinct. If we replace “row” by “column” in the preceding definition, it becomes that of a column complete latin rectangle. A latin rectangle which is both row and column complete is called complete. The following theorem was first proved by Houston(1966) and has already been referred to in Section 2.6. We include it here because of its relevance to latin rectangles (see Theorem 3.1.4 below).

Theorem 3.1.3

If there exists a permutation of the integers 0, 1, 2, …, n − 1 with the property that the differences (taken modulo n) between pairs of adjacent integers are all distinct, then there exists a row complete latin square of order n.

The proof is the same as that of Theorem 2.6.1 and will be omitted.

The complete latin square L constructed by the method of Theorem 3.1.3 is a Cayley table for the cyclic group of order n. However, by Theorem 2.6.3, complete latin squares based on abelian groups of odd order do not exist. It follows that a permutation of the integers 0, 1, 2, …, n − 1 to satisfy Theorem 3.1.3 does not exist when n is odd.

From Theorem 3.1.3 we deduce that, in particular, a latin square of order n = 2m whose first row is 0, 1, 2m − 1, 2, 2m − 2, …, k, 2m − k, …, m + 1, m and whose i-th row is obtained from the first by adding i − 1 modulo n is a row complete latin square. When we construct this latin square, we find that its last m rows are the same as the first but in reverse order. (See Figure 3.1.1.) It follows that the first m rows form a row complete m × 2m latin rectangle. Consequently, we have:

Theorem 3.1.4

Row complete m × 2m latin rectangles exist for every positive integer m.

We note that each such latin rectangle R defines a decomposition of the complete undirected graph K _2m on 2m vertices into m disjoint Hamiltonian paths. If the vertices of K _2m are labelled by the digits 0, 1, …, 2m − 1, then the rows of R define the Hamiltonian paths.

There are further connections between Theorem 3.1.4 and graph decompositions. If we adjoin an additional digit 2m to each row of R to obtain an m × 2m + 1 rectangle R′ and then read the rows of R′ cyclically, they define a decomposition of the complete undirected graph on 2m + 1 vertices into Hamiltonian cycles. If instead of reading these rows cyclically, we read them successively from left to right with the last row followed by the first, they define an Eulerian circuit of the latter graph. [See Figure 3.1.2 and Keedwell(1974).]

There is another interesting application of the augmented rectangle R′. In his book on Recreational Mathematics, Lucas(1883) discussed the problem of devising a performance of successive children’s dances in each of which every child would hold hands with his/her two immediate neighbours so that the participants would together form a closed circle. All the children were to take part in every dance and it was required to arrange them in successive dances in such a way that each child would be neighbour to every other exactly once during the complete performance. Evidently the number n of children participating would have to be odd because any particular child would be neighbour to two others in each dance and so would dance with, say 2m, other children all together. The number of dances is then m and the total number of children is 2m + 1.

It is easy to see that, if the children are named 0, 1, …, 2m, then the Hamiltonian cycles described above provide a solution to the problem. Lucas attributes this solution to C.Walecki though that gentleman obtained his solution by a different method. The Walecki solution has prompted Preece(1994) to remark that the Williams’ sequencing which we described in Theorem 2.6.1 had been obtained much earlier.

For more recent work on this topic and its application to Statistical designs, see Bailey, Ollis and Preece(2003).

Before changing the topic, we should like to pose two problems connected with complete latin rectangles:

(1) if n is a given odd integer, what is the maximum value of m_n such that a complete latin rectangle of size m_n × n exists?
(2) for which values of k_n is it true that an arbitrary complete latin rectangle of size k_n × n can be completed to a complete latin square of order n?

Next, we mention the concept of an (n, d)-complete rectangle.

Definition

An array is called an (n, d)-complete rectangle if it contains n different symbols each of which appears exactly d times in the array, and such that no symbol is repeated in any row or column.

As an example, we note that the 6 × 6 rectangle shown in Figure 3.1.3 is (9,4)-complete.

Up to the present, interest seems to have centred on the case d = 1. In particular, one of the authors of [DK1] has proved the following theorem, in which a rectangle is considered to be trivial if it consists of a single row or a single column:

Theorem 3.1.5

If L is the latin square representing a multiplication table of a group G of order n, where n is a composite number, then L can be split into a set of n non-trivial rectangles each of which is (n, 1)-complete.

Proof

If n is a composite number, G has at least one proper subgroup A ₀, of order h say. By Lagrange’s theorem, G splits into disjoint cosets of A ₀, say A ₀, A ₁, …, A_k ₋₁, where n = hk.

By selecting one element from each of these k cosets, we get a set of coset representatives of G relative to A ₀. It is evident that one can select (in many ways) h such sets of coset representatives which are pairwise disjoint and which together cover G. Call these sets of coset representatives R ₁, R ₂, …, R_h .

Now let a multiplication table for G be formed by taking as row border the elements of the cosets A ₀, A ₁, …, A_k ₋₁ in order and as column border the elements of the sets of coset representatives R ₁, R ₂, …, R_h in order. By the properties of coset representatives, the rectangle whose row border comprises the elements of the coset A_i and whose column border comprises the elements of the set R_j contains each element of G exactly once and is an (n, 1)-rectangle. Hence the multiplication table of G is the union of n such (n, 1)-rectangles. □

As an example, we show in Figure 3.1.4 the result of carrying out the construction for the cyclic group of order 8 when regarded as the additive group of integers modulo 8, with the subgroup {0, 2, 4, 6} as A ₀. We have A ₁ = {1, 3, 5, 7} and we may take (for example) R ₁ = {0, 1}, R ₂ = {2, 5}, R ₃ = {4, 3}, R ₄ = {6, 7}.

The converse of Theorem 3.1.5 is false as is shown by the latin square of order 27 given in Figure 1.6.4. This latter latin square represents a multiplication table for a quasigroup which is not a group but, despite this, it can be split into 27 (27,1)-rectangles.

We turn now to another generalization of the latin square concept which D.A.Norton(1952a) called a row latin square.

A row latin square is a square matrix of order n say, each of whose rows is a permutation of the same n elements. A column latin square is similarly defined. These concepts are related to that of a latin rectangle by the fact that a union of latin rectangles each having n columns (and such that the total number of rows is n) is obviously a row latin square. However, a row latin square cannot necessarily be separated into latin rectangles except in a trivial way.

It is clear that a square matrix which is both a row latin square and a column latin square is a latin square.

Let R be a groupoid satisfying Sade’s left translation law [identity (17) of Section 2.1] then clearly the multiplication table of R is a row latin square. Similarly, the multiplication table of a groupoid R′ satisfying Sade’s right translation law is a column latin square.

Let R be a row latin square bordered by its elements taken in natural order. Then the i-th row of the square determines a permutation P_i of the top border and the square is completely determined by giving the permutations P ₁, P ₂, …, P_n . The product of two row latin squares A and B, which are represented by the permutations P ₁, P ₂, …, P_n and Q ₁, Q ₂, …, Q_n may be defined as the square matrix C = AB = (P ₁ Q ₁, P ₂ Q ₂, …, P_nQ_n ) whose i-th row is given by the product permutation P_iQ_i . Then C is again a row latin square.

Such a representation seems likely to be very useful for quasigroups since, as Suschkewitsch(1929) observed, there are quasigroups whose right (or left) representation forms a group. Such a quasigroup is isomorphic to a quasigroup (G, ·) obtained from an appropriate group (G, ο) by a relation of the form x · y = (xα ⁻¹ ο y)α, where α is an arbitrary fixed permutation of G. If both the right and left representations of a quasigroup form groups, the quasigroup is a group.

We shall give an example of a quasigroup Q whose right representation is a group but whose left representation is not a group.

Take Q to be the quasigroup of order four whose multiplication table is given by Figure 3.1.5. Then clearly the right representation of Q consists of the permutations (1)(2)(3)(4), (1 4)(2 3), (1 2)(3 4), (1 3)(2 4) and these form a group. However, the left representation of Q is not a group since it contains an element (1)(2 4 3) which is of order three. We constructed Q from the Klein group of order four using the rule of Suschkewitsch and by taking

α = ( 1 2 3 4 2 3 1 4 ) .

si2_e

The representation of a quasigroup by means of the permutations defined by the corresponding latin square has been found useful by the present author in work on finite projective planes.

Some of the results published by Norton(1952a) will now be stated without proof.

The set of all row latin squares of order n forms a group of order (n!) ⁿ under the product operation defined above. This group is isomorphic to the direct product of n symmetric groups of degree n.

Let p〈n〉 be given inductively by p〈1〉 = 1, p〈2〉 = 2, and p〈n〉 = p〈n − 1〉 + (n − 1)p〈n − 2〉 for n > 2. The number of row latin squares L of order n which have the property that every row of L ² is represented by the identity permutation, that is,

is [p〈n〉] ⁿ . The number of normalized row latin squares which have this same property is [p〈n − 2〉] ⁿ ⁻¹.

In Norton(1952a), it has been shown that the existence of sets of mutually orthogonal latin squares (see Chapter 5 for the definition of this concept) is dependent upon the parallel problem for row latin squares. Consequently, existence problems concerning sets of the former squares may be studied in terms of the latter.

Theorem 3.1.6

A row (respectively column) latin square which satisfies the quadrangle criterion and is such that at least one among its elements occurs in one of the cells of every column (resp. row) is necessarily a latin square.

Proof

This result is a consequence of the well-known theorem that an associative groupoid must be a group if it has a left identity element and each of its elements has a left inverse.

In the present case, we take the element which occurs in every column as the left identity element (by bordering the square appropriately) and we easily see that then every element has a left inverse with respect to this identity. □

3.2 Critical sets and Sudoku puzzles

In Nelder(1977), in a very short note, that author asked a question about partially completed latin squares which appears deceptively simple to resolve and which we shall now discuss. (He has informed the present writer that he had no particular application in mind but thought the problem interesting.) Let us look at the 3 × 3 partially filled arrays in Figure 3.2.1. We observe that (i) each array is completable to a unique latin square on the three symbols 0, 1, 2 but that (ii) if any one entry is deleted from either array, that array is no longer uniquely completable to such a latin square. Nelder called a set of entries with these two properties a critical set. He asked, for a given latin square of order n, what is the size (number of entries) of a smallest critical set and what is the size of a largest critical set? He denoted these two numbers by scs(n) and lcs(n) respectively.

The first surprise is that critcal sets of different sizes exist for the same latin square; the second is that different latin square of the same order n have smallest critical sets of different sizes. These remarks are illustrated in Figure 3.2.2 and Figure 3.2.3. The critical sets A and B both complete uniquely to the same latin square L ₁ but have different sizes. The critical set C completes uniquely to the latin square L ₂. A is a smallest critical set for L ₁ and C is a smallest critical set for L ₂ but C is larger in size (five entries) than A (four entries). We justify below that A and C are smallest.

However, a smallest critical set for the square L ₃ (which differs from L ₂ in just one intercalate) has only four entries. In fact, the latin squares L ₁ and L ₃ are both isotopes of the cyclic group Z ₄ (and so have smallest critical sets of the same size) whereas L ₂ is isotopic to the 2-group Z ₂ × Z ₂.

Let us now explain why A, C are respectively smallest critical sets for L ₁, L ₂. In any Cayley table of the cyclic group, each element belongs to exactly one intercalate. There are four intercalates all together and no two of them have any cell in common. If the cells of a critical set did not include at least one cell of each intercalate, it would be possible to obtain two completions of that set, one to L ₁ and one to a latin square which differs from L ₁ in having the two distinct symbols of the “uncovered” intercalate interchanged. Since there are four non-overlapping intercalates, there must be at least four cells in a critical set.

The latin square L ₂ has a different arrangement of intercalates. Each cell lies in three different intercalates of L ₂. Since there are 16 cells altogether but each intercalate has four cells, the total number of intercalates is (16 × 3)/4 = 12. The cells of a critical set must contain at least one cell of each of these twelve intercalates. This can be achieved by means of a transversal of the square. The cells of L ₂ which are shown in bold in Figure 3.2.3 form such a transversal. However, these cells alone (or those of any other transversal) are not sufficient for unique completion of L ₂. Figure 3.2.4 shows two different ways in which the remaining twelve cells can be filled, so we need at least one further cell in our critical set. It is easy to check that one appropriately chosen further cell is sufficient to ensure unique completion.

Figure 3.2.4 is an example of a concept which is now called a latin bitrade. (In the early days of this subject, several other terms were used, see later.) This consists of two (juxtaposed) partial latin squares P ₁ and P ₂ such that (i) the same cells are filled in each; (ii) no cell has the same entry in P ₁ as it does in P ₂; (iii) the same entries occur in each particular row of P ₁ as occur in the corresponding row of P ₂; and (iv) the same entries occur in each particular column of P ₁ as occur in the corresponding column of P ₂.

Each of P ₁ and P ₂ is called a latin trade. (In earlier papers, the term latin trade was often used for the pair P ₁, P ₂.)

Suppose that a given latin square L contains P ₁ as a part. Then, if the entries of P ₁ are deleted, the remaining partial square H can be completed in two ways according as the entries of P ₁ or the entries of P ₂ are placed in the empty cells of H. It follows that a critical set for L must include at least one cell of every latin bitrade that has its P ₁ (or P ₂) part included in L. Thus, the study of latin bitrades plays a crucial role in the investigation of critical sets. An intercalate is just the P ₁ part of a 2 × 2 latin bitrade.

Before proceeding further, we need a few formal definitions. It is convenient for this purpose to think of a latin square of order n as consisting of n ² ordered triples (row, column, symbol) as we did in Section 1.4. Usually, we shall use 0, 1, …, n − 1 as our symbols so that rows and columns will be labelled from 0 to n − 1.

A uniquely completable set (UC set) U of triples is such that it characterizes only one latin square. That is, there is a unique latin square of assigned order n which has U as a subset of its triples. Such a set U of triples is said to be a critical set if no subset of U is uniquely completable. Thus, as we showed above, the sets U ₁ = {(0, 0, 0), (0, 1, 1), (1, 0, 1), (3, 3, 2)} and U ₂ = {(0, 0, 0), (0, 1, 1), (0, 2, 2), (1, 0, 1), (1, 1, 2), (2, 0, 2)} are both critical sets for the Cayley table K of the cyclic group Z ₄ and U ₁ is a minimal critical set for K.

In the process of completing a UC set U to the latin square L which it characterizes, we say that adjunction of a triple t = (r, c, s) is forced in the process of completion of a set T of triples (|T| < n ², U ⊆ T ⊂ L) to the complete set of triples which represents L (and which we also write as L), if either

(i) ∀r′ ≠ r, ∃z ≠ c such that (r′, z, s) ∈ T or ∃z ≠ s such that (r′, c, z) ∈ T (that is, in the partial completion F of L, where F is the partial latin square formed by the triples of T, each cell of column c except that in row r is either in a row of F which already contains the symbol s or else is already filled with an element z distinct from s), or
(ii) ∀c′ ≠ c, ∃z ≠ r such that (z, c′, s) ∈ T or ∃z ≠ s such that (r, c′, z) ∈ T such that (r, c, z)eT (that is, in the partial completion F of L, each cell of row r except that in column c is either in a column of F which already contains the symbol s or else is already filled with an element z distinct from s), or
(iii) ∀s′ ≠ s, ∃z ≠ r such that (z, c, s′) ∈ T or ∃z ≠ c such that (r, z, s′) ∈ T (that is, in the partial completion F of L, every symbol except s already occurs either in column c or else in row r of F).

A UC set U is called strong if we can define a sequence of sets of triples U = F ₁ ⊂ F ₂ ⊂ …, ⊂ F_r = L such that each triple t ∈ F_υ ₊₁ − F_υ is forced in F_υ . It is super strong if the adjunction of each triple is forced by virtue of (iii) alone.

A UC set which is not strong is called weak. In particular, a critical set may be weak or strong. A recent refinement of the latter concept is to say that a critical set is totally weak if there is no triple whose adjunction is forced initially rather than only at a later stage of the completion to a unique latin square. See Adams and Khodkar(2001).

Clearly, if the subset U of cells of a latin square L form a UC set for L then those cells of any latin square L′ isotopic to L onto which the cells of U are mapped form a set U′ which is UC for L′ and is of the same type relative to L′ as U is relative to L: that is, weak or strong, critical or minimal critical or neither. We shall regard the sets U and U′ as equivalent.

In order to determine whether a given set S of triples is UC for a given latin square L, we need to check that the triples of S include at least one cell/triple of every latin trade which L contains. Thus, the study of latin trades plays a crucial role in the investigation of UC and/or critical sets as we have already remarked. An intercalate is a latin trade of smallest possible size.

Let us mention here that among earlier names used for a latin trade were critical partial latin square and latin interchange. The latter was used by Drápal [see Drápal and Kepka(1985), for example] and the former in several papers of the present author.

In our further discussion of this topic, we shall look first at critical sets in group-based latin squares.

Very early in the development of the subject of critical sets, in a private letter to Jennifer Seberry, Nelder(1979) conjectured that, for a latin square based on the cyclic group (Z_n , +), a set consisting of two appropriately sized triangles in the top left and bottom right corners of the square would be a smallest critical set. For n odd, these two triangles would each have (n ² − 1)/8 cells; for n even, one would have (n ² +2n)/8 cells and the other (n ² − 2n)/8 cells. (See Figure 3.2.5 for an illustration.) Thus, the size of a smallest critical set based on the cyclic group would be ⌊n ² /4⌋.

Also, Nelder conjectured that a set of n(n − 1)/2 cells consisting of the upper left triangular portion of the square but excluding its main right-to-left diagonal (as in the square of Figure 3.2.6) would be a largest critical set. It has been proved that the first conjecture is correct for cyclic latin squares of even order and for strongly completable critical sets in cyclic latin squares of odd order. This conclusion is arrived at as follows:

The critical sets suggested by Nelder are strongly completable and it was proved by Bate and Van Rees(1999) that the sizes of strongly completable critical sets are bounded below by ⌊n ²/4⌋. Also, Curran and Van Rees(1979) had proved much earlier that, when n is even, a critical set must have size at least n ²/4 (in order to cover all the intercalates) and that the set comprising triangles of sizes (n ² + 2n)/8 and (n ² − 2n)/8 is critical. Then, Cooper, Donovan and Seberry(1991) proved that, when n is odd, the set consisting of two triangles each of size (n ² − 1)/8 is likewise critical.

The possibility remains that, for a cyclic latin square of odd order, a weakly completable critical set of size less than ⌊n ²/4⌋ might exist.

In a long paper involving the use of many latin trades, Donovan and Cooper (1996) succeeded in showing that Nelder’s candidate for a largest critical set in a cyclic latin square is indeed critical though it is still not known whether it is of largest size for such a square. However it is known and had been shown much earlier by Stinson and van Rees(1982) that this critical set is not in general largest for a given size of latin square. In particular, there exist latin squares of orders 6, 7, 8 with critical sets of sizes at least 18, 24, 37 respectively. Questions regarding the sizes of largest critical sets are mostly open.

To summarize, Nelder’s construction for a smallest strongly completable critical set in a cyclic latin square is a construction valid for all orders n.

However, attempts to provide similar constructions of minimal critical sets for other classes of latin square have, so far as the present author is aware, been unsuccessful. Constructions which give critical sets of latin squares based on the dihedral and dicyclic groups have been obtained but these are not minimal for general values of n. For details, see Keedwell(2004).

Next, we turn to the problem of weakly completable critical sets.

A problem which until recently seemed particularly difficult to solve was that of finding, and finding the minimal sizes of, weakly completable critical sets. In Keedwell(1999), it was shown by exhaustive argument that weakly completable critical sets do not exist in the latin squares of orders three and four. Later, by computer [see Bedford and Johnson(2000)], it was also shown that they do not exist in the isotopy class of latin squares based on the cyclic group of order five. On the other hand, they do exist in the only other isotopy class of latin squares of order five. Examples were found by Burgess(2000) who also showed how to construct, for any chosen order, a latin square which contains a weakly completable critical set.

More recently, Bedford and Johnson(2000, 2001) showed that all latin squares based on cyclic groups of orders greater than five have weakly completable critical sets, thus disproving a conjecture of the present author [see page 237 of Keedwell(1996)]. Also, in the first paper, they proved the much stronger result that a weak uniquely completable set exists in every group-based latin square of order greater than five. Clearly, by successive deletion of unnecessary entries, such a uniquely completable set can be reduced to a critical set which is weakly completable. However, the initial steps in the completion of such a critical set to the unique latin square which it defines may then be forced. Observation of this fact led Adams and Khodkar(2001) to introduce the notion of a totally weak critical set that is, one for which initially no empty cell has its entry forced.

For further details of the work of Adams and Khodkar, see Keedwell(2004) and the relevant papers cited therein.

In or about 1979, the freelance puzzle-maker Howard Garns invented a new puzzle originally called “Number Place” for Dell Magazine of New York. This consisted of a 9 × 9 square in the form of nine 3 × 3 subsquares and in which a subset of the 81 cells were already filled with numbers from the set S = {1, 2, …, 9}. The puzzle-solver was required to fill the remaining cells with numbers from the set S in such a way that the completed square would be a latin square L and so that each of the nine 3 × 3 subsquares would contain each of the numbers in the set S just once. In our language, the given filled cells formed a UC set for L which was intended to be strongly completable. Two examples of such puzzles are given in Figure 3.2.7. Later, the puzzle became very popular in Japan and later still, it was promoted under the Japanese name of “Sudoku” to “The Times” newspaper in Great Britain by a New Zealander by the name of Wayne Gould (who had come across the puzzle on a visit to Japan). An initial example of this “Sudoku puzzle” was published in “The Times” in November 2004.

Subsequently, many versions of the puzzle have appeared in many publications throughout the World. In particular, the size of the puzzle square has been generalized to n ² × n ² and such a square is separated into n n × n subsquares. (Usually, n = 3, 4 or 5.) When all the cells of such a square have been filled, it becomes an example of a latin square of order n ² separated into n ² subsquares of order n each of which is (n ², 1)-complete. We shall call such a square a Sudoku latin square and such squares will arise again in Section 5.3 and Section 6.3.

Sudoku latin squares which are group-based can be constructed by the method of Theorem 3.1.5. However, squares obtained in this way are too regular to be used in Sudoku puzzles.

A key question for mathematicians is “What is the size of a minimal critical set for a Sudoku latin square L whether group-based or not?” For the original 9×9 puzzle, it is believed that 17 given entries is minimal. Recently, McGuire(2012) has claimed that he has proved by exhaustive enumeration of cases with the aid of a computer that this is so but, so far as the present author is aware, that claim has not been independently checked. In most published puzzles, the given filled cells form a strongly completable UC set which is neither minimal nor critical. In Figure 3.2.7, the first example is of a typical puzzle square while the second is one of many obtained by computer or otherwise which has just 17 filled cells. We give the following hint for commencing the completion of the latter. The cell (3, 9) must contain 5 because 5 cannot occur in the second row or eighth column but must occur in the subsquare (1, 3). Also, the cell (8, 9) must contain 1 because 1 cannot go elsewhere in the eighth row. [Note that 1 already occurs in the subsquare (3, 2).] Observe that completion would be impossible without the extra requirements for the completed square to be a Sudoku square.

In the 1990’s, Sudoku latin squares with the additional property that both main diagonals contain each symbol just once were introduced and studied (under the name of perfect latin squares) outside the Sudoku puzzle environment in connection with the electronic storage and retrieval of n ² × n ² arrays (e.g. pictures). If such an array is to be stored using only n ² memory modules, then retrieval of a particular set of items (e.g. pixels) is said to be “conflict free” if the required data can be accessed without the necessity to collect more than one item from any particular memory module. It is usually particularly important that retrieval of the items which form a row, column, diagonal or subsquare of the array should be conflict free. This can be achieved by using the symbols of a perfect latin square to specify for each location in the array into which memory module it should be put.

Full details of this application can be found in Kim and Prasanna Kumar(1993) and in Heinrich, Kim and Prasanna Kumar(1992). Prasanna Kumar et al devised a fairly complicated method for constructing perfect latin squares but a somewhat simpler one was given later in Keedwell(2007) although at that time the latter author was unaware of the application just described.

Let us return to the general topic of critical sets and latin bitrades.

A lot of work has been done on trying to determine for which sizes critical sets exist in particular kinds of latin square. In Donovan(1999), that author gave a reference list of known results (up to the date of her paper) on the possible sizes of critical sets for various types of latin square. Later, in a joint paper, Donovan and Howse(2000) gave constructions by means of which they showed that, in suitable latin squares of order n, critical sets exist of all sizes between ⌊n ²/4⌋ and (n ² − n)/2. [See also Donovan and Bean(2000) for a missing case.] A number of questions remain open in regard to this topic. In particular, what is the largest size which a critical set in a latin square may have? For more details, see Keedwell(2004).

A related question is to find the spectrum for the sizes and types (or shapes) of latin bitrades. (By the size of a latin trade, we mean the number of its filled cells. By its shape, we mean the way in which these filled cells are arranged.) In addition, there may be several kinds of latin trade of the same size and type/shape.⁴ For example, in Figure 3.2.8 we exhibit four kinds of latin bitrade of the same size and type. (Three of these have the same shape.) An early attempt to resolve this question was made by the present author [see Keedwell(1994)] who set out to enumerate first the possible types and then the possible kinds of each type for sizes m up to m = 10. However, there were a few omissions in the latter listing which were later filled by Donovan, Howse and Adams(1997). In fact, the same question had been investigated from a quite different point of view much earlier by Drápal and Kepka(1983,1985). These authors had treated a latin trade and its mate as a pair of partial groupoids. Again we refer the reader to Keedwell(2004) for more details.

A considerable amount of work has been done on finding upper and lower bounds for the minimal size gdist(n) of a latin trade in a group-based latin square of order n. For an integer n ≥ 2, let gdist(n) denote the minimum distance between two groupoids (Q, ο) and (Q, ·) as (Q, ο) varies through all quasigroups of order n and (Q, ·) varies through all groups of order n. It is immediate to see that gdist(n) is the quantity whose bounds we are seeking. Drápal and Kepka(1989) obtained the result gdist(n) ≥ 3 + e log _e p for n equal to the prime p (which implies that the latin square is cyclic) and, later, Cavenagh(2003) obtained the almost identical result gdist(n) ≥ ⌈2 + e log _e p⌉ by a simpler and more direct method. Again, we refer the reader to Keedwell(2004) for details.

More recent work on latin trades and/or bitrades has focussed on the geometrical and topological representation of the latter. This work also was initiated by Drápal(1991,2001) who conceived the idea of representing a latin bitrade by an orientable surface⁵ and hence giving it a genus.

In order to introduce the idea, we shall think of a latin square in its guise as the multiplication table of a quasigroup. Let (Q, ★) and (Q, ο) be two quasigroups of order n defined on the same set Q and put M = {(a, b) ∈ Q × Q, a★b ≠ a ο b}. That is, the elements of M are the entries in the cells of the latin bitrade that transforms (Q, ★) to (Q, ο) and conversely. This is made clear by Figure 3.2.9 wherein, for example, the elements (2, 0) and (0, 2) of M arise from the second row of the latin bitrade. Thus, M is the size of the latin bitrade as defined earlier.

We define a set Δ(★, ο) of triangles such that their vertices are elements of M and each triangle has vertices of the form (a, b), (c, b), (a, d), where a ★ b = c ο b = a ο d. We define a row permutation ρ by (a, b)ρ = (a, d), where a ★ b = a ο d, and a column permutation μ by (a, b)μ = (c, b), where a ★ b = c ο b. Lastly, we define an element permutation γ by γ = ρ ⁻¹ μ.

The following facts are easily proved:

(1) If (a, d) ∈ M and (a, d)γ = (c, b), then c ο b = a ο d.
[(a, d)γ = (c, b) ⇒ (a, d)ρ ⁻¹ = (c, b)μ ⁻¹ and (a, d) ∈ M implies that there is an element b ∈ Q such that a ο d = a ★ b (b ≠ d) Then (a, d)ρ ⁻¹ = (a, b). It follows that (c, b)μ ⁻¹ = (a, b) so c ο b = a ο d.]
(2) For every triangle Δ ∈ Δ(★, ο), there is exactly one ordered pair l ∈ M such that Δ = {l, lμ, lρ}, where l = (a, b) say.

Hence, there is exactly one triangle of Δ(★, ο) with vertices {l, lμ, lρ} or {m, mρ ⁻¹, mγ} where m = lρ, or {n, nγ ⁻¹, nμ ⁻¹} where n = lμ.

It follows that each vertex m ∈ M occurs in at most three triangles of Δ(★, ο) and that these triangles when they exist and are distinct are {m, mμ, mρ}, {m, mρ ⁻¹, mγ} and {m, mγ ⁻¹, mμ ⁻¹}.

It is easy to show that, for a fixed m, no two of these triangles coincide.

Theorem 3.2.1

All connected components of the polyhedron induced, by Δ(★, ο) are orientable surfaces.

Proof

We orient each triangle in the order (m, mμ, mρ). Then we define the faces of the polyhedron to be these triangles and also the orbits of the permutations ρ ⁻¹, μ and γ ⁻¹ (where cycles of length 2 are represented as “faces” with two edges). Each edge is then a side of exactly one triangle {m, mμ, mρ} and exactly one orbit and adjacent faces are oriented in the same way (clockwise or anti-clockwise). □

Since three triangles and three orbits meet at each vertex, the vertices have valency six. There are |M| vertices, so the number of triangles is |M| and the number of edges is 3|M|. Since each cycle of an orbit of ρ, μ ⁻¹ and γ defines a face of the polyhedron, the total number of faces (including those formed by the triangles) is |M| + ω(ρ) + ω(μ) + ω(γ), where ω(θ) denotes the number of cycles of the permutation θ.

Example

Let Q = {0, 1, 2, 3} and the quasigroups (Q, ★) and (Q, ο) be defined as shown in the left-hand diagram of Figure 3.2.9 .

We find that the triangles are

	m		→		mμ	→	mρ
(1)	b ₂ ★ c ₂	=	2	=	b ₃ ο c ₂	=	b ₄ ο c ₄
(2)	b ₂ ★ c ₄	=	0	=	b ₃ ο c ₄	=	b ₂ ο c ₂
(3)	b ₃ ★ c ₁	=	2	=	b ₄ ο c ₁	=	b ₃ ο c ₂
(4)	b ₃ ★ c ₂	=	3	=	b ₄ ο c ₂	=	b ₃ ο c ₁
(5)	b ₃ ★ c ₃	=	0	=	b ₄ ο c ₃	=	b ₃ ο c ₄
(6)	b ₃ ★ c ₄	=	1	=	b ₄ ο c ₄	=	b ₃ ο c ₃
(7)	b ₄ ★ c ₁	=	3	=	b ₃ ο c ₁	=	b ₄ ο c ₂
(8)	b ₄ ★ c ₂	=	0	=	b ₂ ο c ₂	=	b ₄ ο c ₃
(9)	b ₄ ★ c ₃	=	1	=	b ₃ ο c ₃	=	b ₄ ο c ₄
(10)	b4 ★ c ₄	=	2	=	b ₂ ο c ₄	=	b ₄ ο c ₁

The permutations are

(a) row orbits (ρ):
- (b ₂, c ₂) → (b ₂, c ₄) → (b ₂, c ₂)
- (b ₃, c ₁) → (b ₃, c ₂) → (b ₃, c ₁)
- (b ₃, c ₃) → (b ₃, c ₄) → (b ₃, c ₃)
- (b ₄, c ₁) → (b ₄, c ₂) → (b ₄, c ₃) → (b ₄, c ₄) → (b ₄, c ₁)
(b) column orbits (μ):
- (b ₂, c ₂) → (b ₃, c ₂) → (b ₄, c ₂) → (b ₂, c₂)
- (b ₂, c ₄) → (b ₃, c ₄) → (b ₄, c ₄) → (b ₂, c ₄)
- (b ₃, c ₁) → (b ₄, c ₁) → (b ₃, c ₁)
- (b ₃, c ₃) → (b ₄, c ₃) → (b ₃, c ₃)
(c) element orbits (γ) in (Q, ο):
- (b ₂, c ₂) → (b ₃, c ₄) → (b ₄, c ₃) → (b ₂, c ₂)
- (b ₂, c ₄) → (b ₃, c ₂) → (b ₄, c ₁) → (b ₂, c ₄)
- (b ₃, c ₁) → (b ₄, c ₂) → (b ₃, c ₁)
- (b ₃, c ₃) → (b ₄, c ₄) → (b ₃, c ₃)

Hence we obtain the polyhedron shown in Figure 3.2.10.

In general, if g is the genus of a surface, then υ − e + f = 2 − 2g. We have

υ = | M | , e = 3 | M | , f = | M | + ω ( ρ ) + ω ( μ ) + ω ( γ ) . Thence , 2 g = 2 − υ + e − f = 2 + | M | + ω ( ρ ) − ω ( μ ) − ω ( γ ) .

si3_e

If ω(ρ) ≥ 1 + |M|/3, ω(μ) ≥ 1 + |M|/3 and ω(γ) ≥ 1 + |M|/3, then g < 0 so at least one of one of ω(ρ), ω(μ), ω(γ) is less than 1 + |M|/3.

If ω(ρ), ω(μ) and ω(γ) are all less than |M|/3, then g ≥ 1.

In the case when g = 0, ω(θ) ≥ |M|/3 for at least one θ (θ = ρ, μ, or γ) so at least one cycle has length 2 (since θ acts on |M| symbols): that is, mθ ² = m for some m ∈ M. This fact is illustrated by Figure 3.2.10.

In Drápal(2003) and in subsequent publications, that author has pointed out that any latin bitrade can be replaced by a canonical latin bitrade (called a separated latin trade by Drápal) in which the rows, columns and symbols are in one-to-one correspondence with the cycles. For example, the latin bitrade in Figure 3.2.9 can be replaced by one in which the second row is replaced by two rows, one having the entries 2₃ and 3₂ in the first two columns and the other 0₁ and 1₀ in the last two columns. The column and symbol maps which involve more than one cycle can be separated in the latin bitrade in a similar manner. This is illustrated by Figure 3.2.11 in which, reading from left to right, the diagrams show firstly the original latin bitrade, secondly the same bitrade “element separated”⁶, thirdly “element and row separated”, and finally “fully separated”.

For any separated latin bitrade, we have the interesting result that the sum of the numbers of rows, columns and symbols is less than |M| +3 (since g ≥ 0). Moreover, the numbers of rows, columns and symbols in a separated latin bitrade are equal to ω(ρ), ω(μ), ω(γ) respectively, so it is not necessary to construct the corresponding polyhedron in order to calculate the genus of such a bitrade.

Let us note also that the concept of genus only makes sense if the latin bitrade is connected or indecomposable or primary (all three terms have been used): that is, only if the latin bitrade cannot be decomposed into two or more latin bitrades of smaller size.

Two interesting questions arise. Firstly, what is the size of the smallest latin bitrade which has genus greater than zero; and, secondly, how can we characterize those latin trades which have a particular genus?

The answer to the first question is “size 9 if the bitrade is itself a latin square or size 12 otherwise”. The author is not sure who first observed these facts but Figure 3.2.12 provides examples of such bitrades.

As regards the second question, it had been conjectured for some while that the two component trades of every latin bitrade whose genus is zero could be embedded in abelian groups (as distinct from merely being embeddable in quasigroups) and the truth of this conjecture was proved almost simultaneously by Cavenagh and Wanless(2009) and by Drápal, Hämäläinen and Vitězslav(2010) but using different methods. Later, it was further shown by Blackburn and Mc-Court(2013) that, for a bitrade L = (T, T′) of genus zero, the abelian groups into which T and T′ embed are isotopic. So far as the present author is aware, it is not known whether latin bitrades of genus one or any other genus g > 0 can be characterized in some similar way.

There are a number of facts which are easy to check:

(i) For T (and T′) to be embeddable in the Cayley table of an abelian group, it is sufficient that L = (T, T′) has genus zero but is certainly not necessary.
(ii) Some latin trades can be embedded in the Cayley table of more than one group (none or several of which may be abelian).
(iii) There exist latin bitrades L = (T, T′) of genus g > 0 either only one or neither of whose components T and T′ can be embedded in groups.
(iv) If L = (T, T′) has genus g > 0, T′ and T may be embeddable in different groups but, if T and T′ are isotopic, they can certainly be embedded in isotopes of the same group.

Cavenagh and Wanless(2009) have obtained the smallest connected and separable latin bitrade L = (T, T′) with the property that neither T nor T′ embed in any group since both fail the quadrangle criterion (defined on page 4). We exhibit L in Figure 3.2.13. It is easy to see that the quadrangles whose cells are (b ₂, c ₁), (b ₂, c ₂), (b ₃, c ₁), (b ₃, c ₂) and (b ₁, c ₂), (b ₁, c ₃), (b ₂, c ₂), (b ₂, c ₃) fail the quadrangle criterion in both T and T′. These authors have also obtained the smallest (which has size 14) connected and separated bitrade in which T embeds in a group but not in any abelian group. They have given examples of other interesting situations. Drápal, Hämäläinen and Vitězslav(2010) have given an example of a latin trade of genus one and size 18 which does not itself fail the quadrangle criterion but nonetheless does not embed in any group.

The above remarks raise two further questions. First, the reader will observe that the latin bitrade exhibited in Figure 3.2.14 can be regarded as having been obtained as the union (in some sense) of the latin bitrade shown in the left-hand diagram of Figure 3.2.12 and the intercalate Unlabelled Image by coalescing the cells which contain 2₄ and 4₃ in the respective bitrades to give an amended cell 2₃.

This idea of combining (or “adding”) latin bitrades has been generalized in several different ways. See, in particular, Donovan and Mahmoodian(2002,2003), Drápal(2003) and Cavenagh, Donovan and Drápal(2004).

Secondly, the latin square (group table) of smallest order into which the component T of the latin trade of Figure 3.2.14 can be embedded is cyclic of order six. We may thence ask the general question: “What is the minimal order of a latin square into which a given separated (or non-separated) latin trade T of size h may be embedded?”

A latin bitrade is called minimal if it contains no latin bitrade of smaller size. Lefevre, Donovan, Cavenagh and Drápal(2007) have investigated the minimum size h of a latin bitrade of genus g and, in particular, they have shown that a minimal latin bitrade of genus g and size 8g + 8 exists for each non-negative integer g.

A latin bitrade is called k-homogeneous if it has the same number k of rows, columns and symbols. The latin bitrades exhibited in Figure 3.2.12 are both 3-homogeneous. Because a derangement of three objects necessarily consists of a single cycle, every connected 3-homogeneous latin bitrade has genus one (and also is necessarily in separated form).

Cavenagh, Donovan and Drápal(2005a) have enumerated all 3-homogeneous latin bitrades. [See also Cavenagh(2006).] The latter paper contains another interesting result: namely that every 3-homogeneous latin trade can be partitioned into three disjoint transversals. This fact has subsequently been re-proved several times.

For results concerning 4-homogeneous latin bitrades, see Cavenagh, Donovan and Drápal(2005b) and for more general results concerning k-homogeneous latin bitrades, see Bean, Bidkhori, Kosravi and Mahmoodian(2005) and Behrooz Bagheri and Mahmoodian(2011).

More generally, a latin bitrade has been called (r, c, s)-homogeneous if each row has r entries, each column has c entries and each symbol occurs s times. In Drápal and Griggs(2010), these authors have proved that (r, c, s)-homogeneous latin bitrades of genus one exist only when (r, c, s) = (3,3,3), (4,4,2) or (6,3,2).

There are many further papers on latin bitrades. A fairly comprehensive list of those published up to 2007 is given in a survey paper written by Cavenagh(2008). Also, there exist alternative ways of representing latin bitrades topologically and so obtaining their genus. The simplest of these is as follows:

For the connected and separated latin bitrade L = (T, T′) with rows b ₁, b ₂, …, b_u , columns c ₁, c ₂, …, c_υ and symbols s ₁, s ₂, …, s_w , construct a triangulated pseudo-surface as follows. The vertices are the “names” of the rows, columns and symbols, so there are V = u + υ + w vertices. Corresponding to each occupied cell (b_i , c_j ) of T, construct a triangle with vertices b_i , c_j , s_k , where s_k is the symbol in the cell (b_i , c_j ), and with edges [b_i , c _j ], [c_j , s_k ], [s_k , b_i ] oriented in that order. We call them “black” triangles. Corresponding to each cell of T′, we construct a “white” triangle according to the same rule. Since each symbol which occurs in row b_i of T also occurs in row b_i of T′ and since the same statement is true for the columns, each edge is a side of two triangles, one black and one white, so the total number E of edges is one half of three times the number of triangles. The total number F of triangles (faces) is 2|M|, where |M| is the size of T (or T′). Hence, the genus g satisfies 2g = 2 − (V − E + F) = 2 − (u + υ + w − 3|M| + 2|M|) = 2+ |M| − ω(ρ) − ω(μ) − ω(γ) which is the same as we obtained for the earlier representation.

The black and white triangle representation of a latin bitrade has been, for example, used by Blackburn and McCourt(2013) in their paper mentioned above.

We might ask: “Are there other combinatorial structures which can be represented topologically and hence assigned a genus?”

In the first part of this section, we discussed uniquely completable and critical sets for assigned latin squares. Cameron(1994) has solved a different but related question: “How few positions (cells) in an n × n array have the property that any latin square of order n is uniquely determined by its entries in these particular cells?”

For example, the six cells (1,1), (1,2), (1,3), (2,1), (2,2), (3,1) of a 4 × 4 array do not satisfy the Cameron requirement because, although the left-hand latin square of Figure 3.2.15 is completely determined by its entries in these particular cells (they form a critical set for it), neither of the remaining two squares of Figure 3.2.15, is uniquely determined by its entries in these six cells since the same entries occur in both.

Cameron has given a structural characterization for such a set of cells valid for all n ≥ 3 and has shown that the minimum number of cells in such a set is n(n − 2) except when n = 4. For n = 2, 3, 4, the numbers of cells required are 1, 3, 7 respectively.

In Bartlett(2013), yet another problem concerning completion of partial latin squares has been considered. A partial latin square of order n is ε-dense if each row and column contains at most εn filled cells and each symbol occurs at most εn times. It is conjectured that every 1 4 si4_e -dense partial latin square is completable. (cf. Section 3.4.)

In the next section of this chapter, we consider, for the case of latin squares which are isotopic to group tables, the largest number of randomly chosen elements which we may delete without the resulting partial square losing the property of being uniquely completable.

3.3 Fuchs’ problems

In his book Fuchs(1958), that author raised the following problem: “Let k elements be deleted at random in the Cayley table of a finite Abelian group G of order n. Determine the greatest k = k(n) for which

(a) the rest of the table always determines G up to isomorphism;
(b) the table can be reconstructed uniquely from its remaining part.

The first author of [DK1] gave a solution to problem (b) without the restriction that the group is abelian [see Dénes(1962)]. His result should have been that, for any given group of order n ≠ 4 or 6, we have k(n) = 2n − 1. (In fact, there was an error in his proof and he omitted to exclude n = 6 from the statement, see Theorem 3.3.1 below.)

Thus, unexpectedly, k(n) does not depend on the structure of the group but depends only on its order. For the case n = 4, he obtained the value k(n) = 3.

For the proof, let us begin by pointing out that an abstract group is completely known when each of its elements has been represented by a symbol and the product of any two symbols in each order has been exhibited.

For a finite group, the products may be exhibited conveniently by means of the Cayley table of the group and we may represent the elements of the group by means of the natural numbers 1, 2, …, n. Moreover, as proved in Section 1.1, a matrix ‖a_ik ‖ whose entries are the natural numbers 1, 2, …, n will represent the Cayley table of such a group if and only if (1) it is a latin square and (2) the quadrangle criterion holds, that is, for all subscripts i, j, …, the equalities

a ik = a i 1 k 1 , a il = a i 1 l 1 , a jk = a j 1 k 1 imply a jl = a j 1 l 1 .

si5_e

Further, we may choose an arbitrary row and column of the unbordered Cayley table, say the j-th row and l-th column, and consider them as being the products of the elements by the group identity from the left and from the right respectively by bordering the table with this row and column. Then a_jl will be the identity of the system G_jl thus arising, and necessarily a_ila_jk = a_ik . Now (1) ensures that G _jl is a loop and (2) implies associativity, thus G_jl is a group. Clearly, every group with the same Cayley table arises in this way.

All these G_jl are isomorphic, for a transition from G_jl to G_rs means simply that we take three permutations θ, ϕ, ψ such that ab = c in G_rs if and only if aθ · bϕ = cψ in G_jl : that is, G_jl and G_rs are isotopic and hence, by Theorem 1.3.4, isomorphic groups.

Note that different multiplication tables of a group can be transformed into one another by row and column interchanges.

Definition

If ‖a_ik ‖ and ‖b_ik ‖ are two matrices of the same dimensions, then we call the i-th rows corresponding rows, the k-th columns corresponding columns, and a_ik and b_ik corresponding elements. Also, we define the distance between ‖a_ik ‖ and ‖b_ik ‖, denoted by d(‖a_ik ‖, ‖b_ik ‖), to be equal to the number of cells in which the corresponding elements a_ik and b_ik are not equal.

The distance so defined is a generalization of the original notion of Hamming distance between vectors having binary components which is used in coding theory. See Section 11.4. The above notion of distance was introduced by Lee(1958).

Any permutation may be written as a product of disjoint cycles. If all these cycles have the same length, the permutation is called regular. If, for the permutations σ, τ we have aσ ≠ aτ for exactly k symbols a, then we say that they differ in k places.

We shall need the following lemma concerning permutations.

Lemma

Two regular permutations which differ in exactly two places must be of the form (i ₁ i ₂ ⋯ i_n ) and (i ₁ i ₂ ⋯ i_n _/2)(i _(n/2}+1 i _{(n/2) + 2} ⋯ i_n ).

Proof

Suppose that the permutations ρ and σ differ from each other by a transposition τ = (i_a i_b ) so that σ = ρτ and ρ = στ. Without loss of generality we may assume that the number of cycles in ρ is no more than the number of cycles in σ. Then ρ necessarily has a cycle containing both i_a and i_b and this cycle gets split into two by the action of τ. It follows from the regularity that ρ must consist of a single cycle, say

( i 1 i 2 … i a … i b … i n )

si6_e

and hence that σ = ρτ consists of two cycles

( i 1 i 2 … i a − 1 i b i b + 1 … i n ) ( i a i a + 1 … i b − 1 ) .

si7_e

Since σ is a regular permutation, b − a = n − (b − a) so b − a = n/2 and this, after appropriate re-labelling, proves the lemma. □

Theorem 3.3.1

Two different Cayley tables, A and A′, for the (not necessarily distinct) groups G and G′ of order n ∉ {4, 6}, differ from each other in at least 2n places.

[The authors are grateful to Frisch for pointing out the fact that Theorems 3.2.1 and 3.2.2 as stated in Dénes (1962) and in the first edition of this book were not correct and should be replaced by the one above.]

Proof

Suppose firstly that A and A′ do not have any pair of corresponding rows equal. Then, each pair of corresponding rows differ in at least two places, so in this case A and A′ differ in at least 2n places altogether. Thus, without loss of generality, we may suppose that the x-th row of A is equal to the x-th row of A′ and, by a similar argument, that the y-th column of A is equal to the y-th column of A′. The rows of A (likewise those of A′) are permutations of the x-th row of A (or A′) and these permutations form regular permutation groups P and P′ isomorphic to G and G′ respectively. (This is a variant of the classical result of group theory known as Cayley’s theorem.) Every element of P ∩ P′ represents one of the equal rows in A and A′. It follows that the number s of rows that are the same in A and A′ is equal to the order of the subgroup H = P ∩ P′ and so either s = n/2 or s ≤ n/3 (by Lagrange’s theorem for groups).

Case 1. No pair of corresponding permutations in A and A′ has the form described in the lemma: namely,

ρ = ( i 1 i 2 … i n ) and σ = ( i 1 i 2 … i n / 2 ) ( i ( n / 2 ) + 1 i ( n / 2 ) + 2 … i n ) .

si8_e

(This means that every pair of distinct corresponding permutations differ in at least three places.)

Case 1.1. s ≤ n/3. (When n is odd, only this case can occur.)

In this case, d(A, A′) ≥ 3(n − n/3) = 2n since there are at least n − n/3 pairs of corresponding rows each pair of which differ in at least three places.

Case 1.2. s = n/2. (This case occurs only when n is even.)

We shall show that two regular permutations ϕ and ψ (of degree n) which differ in exactly three places must have one of the two forms below. We use ξ to denote the cycles which ϕ and ψ have in common. Then either,

(a) ϕ = ( i 1 i 2 … i h i h + 1 … i h + j i h + j + 1 … i h + j + k ) ξ , ψ = ϕ ( i 1 i h + 1 i h + j + 1 ) = ( i 1 i 2 … i h i h + j + 1 i h + j + 2 … i h + j + k i h + 1 i h + 2 … i h + j ) ξ where h, j, k ≥ 1, or
(b) ϕ = ( i 1 i 2 … i n / 3 i ( n / 3 ) + 1 … i 2 n / 3 i ( 2 n / 3 ) + 1 … i n ) , ψ = ϕ ( i 1 i ( 2 n / 3 ) + 1 i ( n / 3 ) + 1 ) = ( i 1 i 2 … i n / 3 ) ( i ( n / 3 ) + 1 i ( n / 3 ) + 2 … i 2 n / 3 ) ( i ( 2 n / 3 ) + 1 i ( 2 n / 3 ) + 2 … i n ) .

To see this, assume that ψ = ϕθ where θ consists of a single 3-cycle. We first observe that, if ϕ is regular and the three elements re-arranged by θ come from two or more different cycles of ϕ then ψ is not regular. If they come from three different cycles in ϕ then they lie in the same cycle of ψ and in this case we interchange the roles of ϕ and ψ. So henceforth we may suppose that they come from the same cycle. We can also suppose without loss of generality that the labelling of the symbols is chosen so that

ϕ = ( i 1 i 2 … i h i h + 1 … i h + j i h + j + 1 … i h + j + k ) ξ

si11_e

and the three elements re-arranged by θ are i ₁, i_h ₊₁ and i_h _+j+1. There are two cases to consider; either θ = (i ₁ i_h ₊₁ i_h _+j+1) or θ = (i ₁ i_h _+j+1 i_h ₊₁). The first case leads directly to the form (a) above. In the second case,

ψ = ( i 1 i 2 … i h ) ( i h + 1 i h + 2 … i h + j ) ( i h + j + 1 i h + j + 2 … i h + j + k ) ξ ,

si12_e

which can only be regular if h = j = k. Then, because both ψ and ϕ are regular, we find that ξ must be trivial and this gives us the form (b).

Next, we shall show that, if n > 6, neither of the forms (a) or (b) is possible. Since, in both cases, [P: H] = [P′: H] = 2, both ϕ ² and ψ ² lie in H (since the square of every element of P or P′ must lie in H if the index is 2). Hence also ϕ ² ψ ⁻² ∈ H and so is regular.

Now, if n > 6 and case (b) holds, we have i ₁ ϕ ² ψ ⁻² = i ₃ ψ ⁻² = i ₁ and, because P and P′ consist of regular permutations, we must therefore have ϕ ² ψ ⁻² equal to the identity. But i_n _/3 ϕ ² ψ ⁻² = i _(n/3)+2 ψ ⁻² = i _2n/3 ≠ i_n _/3 which is a contradiction. (If n = 6, i ₁ ϕ ² ψ ⁻² = i ₃ ψ ⁻² = i ₃ so ϕ ² ψ ⁻² is not equal to the identity and no contradiction arises.)

If case (a) holds, ϕ and ψ must consist of only one cycle since otherwise ϕ ² ψ ⁻² ∈ H would fix some symbols and, being regular, would then be equal to the identity whereas i_hϕ ² ψ ⁻² = i_h ₊₂ ψ ⁻² = i_h _+j+k. If n > 6, then one of h, j, k is ≥ 3. Let us suppose that h ≥ 3. Then i ₁ ϕ ² ψ ⁻² = i ₃ ψ ⁻² = i ₁ whereas i_hϕ ² ψ ⁻² = i_h ₊₂ ψ ⁻² = i_h _+j+k ≠ i_h which is contradictory. (Again, if n = 6, no contradiction arises.) If j ≥ 3, i_h ₊₁ ϕ ² ψ ⁻² = i_h ₊₁ whereas i_h _+j ϕ ² ψ ⁻² = i_h . If k ≥ 3, i_h _+j+1 ϕ ² ψ ⁻² = i_h _+j+1 whereas i_h _+j+k ϕ ² ψ ⁻² = i_h _+j.

Thus, when n > 6 and Case 1.2 holds, two different corresponding permutations must differ from each other in at least 4 places and so d(A, A′) ≥ 4(n − n/2) = 2n.

When n = 6 and Case 1.2 holds, it is shown in Note 1 below that a minimum distance of 9 is possible.

Case 2. There exist two corresponding permutations ρ = (i ₁ i ₂ ⋯ i_n ) ∈ P and σ = (i ₁ i ₂ ⋯ i_n _/2)(i _(n/2)+1 i _(n/2)+2 ⋯ i_n ) ∈ P′ as in the lemma. (This case occurs only when n is even.)

Then P = 〈ρ〉 and [P′: 〈σ〉] = 2. Also, using ε to denote the identity element of H, we have P ∩ 〈σ〉 = 〈ε〉 because i _(n/2)−1 ρ^k = i _(n/2)+k−1 and so each cycle of a non-trivial power of ρ contains elements with suffices ≤ n/2 and > n/2. Consequently, H ∩ 〈σ〉 = 〈ε〉 and so all products of the form σ^kγ (where γ ∈ H and 0 ≤ k < n/2) are different. These products all lie in P′; whence (n/2)|H| ≤ |P′| = n. Therefore, |H| ≤ 2. With the exception of the pairs (ρ, σ) and (ρ ⁻¹, σ ⁻¹), there is no other pair of permutations ρ^k = (j ₁ j ₂ … j_n ) ∈ 〈ρ〉 = P and τ = (j ₁ j ₂ … j_n _/2)(j _(n/2)+1 j _(n/2)+2 … j_n ) ∈ P′. For suppose there were such a pair (ρ^k , τ). Then each cycle of τ would contain elements i_u , i_v with u ≤ n/2 and v > n/2 and consequently the non-identity elements of 〈τ〉 would all be distinct from the non-identity elements of 〈σ〉. Because σ, τ ∈ P′, the order of P′ would be at least (n/2)². Since ord P′ ≤ n, this cannot happen except when n = 4.

Also, it is clear that it is only possible for there to be another pair of permutations θ = (j ₁ j ₂ … j_n _/2)(j _(n/2)+1 j _(n/2)+2 … j_n ) ∈ P and η = (j ₁ j ₂ ⋯ j_n ) ∈ P′ if both A and A′ are cyclic (because (i ₁ i ₂ ⋯ i_n ) ∈ P implies that P, and so A, is cyclic and similarly (j ₁ j ₂ … j_n ) ∈ P′ implies that P′, and so A′, is cyclic). When such a pair of permutations θ, η, does exist, at most four pairs of corresponding rows of A and A′ have distance two: namely, those corresponding to the pairs (ρ, σ), (ρ ⁻¹, σ ⁻¹), (θ, η), and (θ ⁻¹, η ⁻¹). In all other cases, at most two pairs of corresponding rows of A and A’ have distance two.

Thus, remembering that |H| ≤ 2, we see that at most two corresponding pairs of rows are the same and at most four pairs of corresponding rows differ in only two places and so d(A, A′) ≥ 3(n − 6) + 4.2 = 3n − 10 if both groups are cyclic and d(A, A′) ≥ 3(n − 4) + 2.2 = 3n − 8 otherwise. We note that 3n − 10 ≥ 2n when n ≥ 10 and that 3n − 8 ≥ 2n when n ≥ 8. However, one can check that two different tables of the cyclic group Z 8 can have at most two pairs of corresponding rows which are at distance two. (See Note 3 below.) Consequently, d(A, A′) ≥ 2n for all n ≥ 8.

When n = 6, the minimal distance d(A, A′) = 3n − 10 = 8 and this distance can be achieved as the following example shows (but only for two tables of Z 6 as is shown in Note 2 below):

When n = 4, any pair of group tables with one pair of corresponding rows and one pair of corresponding columns equal (in all other cases, the tables differ in at least 8 places) can be transformed to standard form using the isotopy operation without changing their distance apart.

The four tables in standard form are as follows:

Of these, the first is the multiplication table of Z 2 × Z 2 and the other three are multiplication tables of Z 4 . The tables of the two different groups differ in four places and the different tables of Z 4 differ in seven places, so d(A, A′) < 2n = 8. This completes the proof of the theorem. □

REMARK. In Drápal(2004), that author has given an alternative proof of this theorem and has dedicated it to the memory of József Dénes. Drápal’s proof makes use of work on the Hamming distance between group tables developed by himself and others: for example, in Drápal(1992,2001) and Donovan, Oates-Williams and Praeger(1997). There is also some connection with Problem 1.1 of [DK1].

In her Ph.D. thesis “Lateinische Quadrate” (Vienna, 1988), Frisch has made the following additional comments [see also Frisch(1997]:

Note 1. Distance 9 between two Cayley tables of the cyclic group Z 6 si18_e can be attained as shown:

In this example, both (163524) ∈ P, (162435) ∈ P′ and (142536) ∈ P, (14)(25)(36) ∈ P′ are pairs of corresponding permutations so both of the forms (a) and (b) of Case 1.2 occur.

However, Case 1.2 with d(A, A′) < 12 can only occur between two different tables of the cyclic group Z 6 si19_e . If G ≅ D ₃, G ′ ≅ Z 6 si20_e and |H| = 3 (as required by Case 1.2) so that P = 〈ε, (1 2 3)(4 5 6), (1 3 2)(4 6 5), (1 4)(2 6)(3 5), (1 5)(2 4)(3 6), (1 6)(2 5)(3 4)〉, then the only possibilities for P′ are 〈(1 4 2 5 3 6)〉, 〈(1 5 2 6 3 4)〉 and 〈(1 6 2 4 3 5)〉. One can check that, in each of these cases, every pair of corresponding permutations outside H differ in at least 4 places.

Note 2. Case 2 for n = 6 with d(A, A′) < 12 can only occur between two different tables of the cyclic group Z 6 si21_e . For, suppose, if possible, that Case 2 holds with G ≅ Z 6 si22_e , G′ ≅ D ₃. Then |H| ≤ 2 and we may suppose without loss of generality that Z 6 = 〈 ( 1 2 3 4 5 6 ) 〉 si23_e and that (1 2 3)(4 5 6) ∈ D ₃. In that case, D ₃ cannot contain (1 4)(2 5)(3 6) because (1 2 3)(4 5 6)·(1 4)(2 5)(3 6) = (1 5 3 4 2 6) ∉ D ₃. Therefore, |H| = 1 and so d(A, A’) ≤ 3(n − 3) + 2 · 2 = 13.

Note 3. If, in two different tables for Z 8 si24_e , (1 2 3 4 5 6 7 8) ∈ P and (1 2 3 4)(5 6 7 8) ∈ P′ form a pair of corresponding permutations which differ in two places, then each of the possible cycles of length 8 which can generate P′ contains at most two integers in a sequence of consecutive even integers and at most two integers in a sequence of consecutive odd integers. (An example is the cycle (1 6273845).) However, the elements of order 4 in P are (1 3 5 7)(2 4 6 8) and (1 7 5 3)(2 8 6 4). It follows from the lemma that any 8-cycle which differs from one of these in only two places must contain sequences of more than two consecutive even integers and more than two consecutive odd integers.

To summarize, if A, A′ are distinct Cayley tables of groups of order n, we have d(A, A′) ≥ 2n in all cases except the following:

d(A, A′) ≥ 4 if the tables are those of the distinct groups Z 2 × Z 2 and Z 4 ;
d(A, A′) ≥ 7 if the tables are both tables of the group Z 4 ;
d(A, A′) ≥ 8 if the tables are both tables of the group Z 6 and Case 2 holds;
d(A, A′) ≥ 9 if the tables are both tables of the group Z 6 and Case 1.2 holds.

Theorem 3.3.2

For a group of order n (n ≠ 4 or 6), we have k(n) = 2n − 1 [where k(n) is defined as at the beginning of this Section].

Proof

Let us delete 2n − 1 arbitrary elements in a Cayley table A of the group G of order n (n ≠ 4 or 6). Suppose that there is a Cayley table A′ ≠ A of G having the property that the rest of A may be completed to A′. Then, clearly, A and A′ differ in no more than 2n − 1 places, which is impossible, by Theorem 3.3.1.

We have to prove further that we can delete 2n elements of a Cayley table A of a group G of order n in such a way that the rest of the table may be completed to a Cayley table A′ different from A. If we interchange two arbitrary symbols, a and b, throughout A, then we shall obtain a new Cayley table differing from A in exactly 2n places and which still satisfies the quadrangle criterion. So the proof of our statement is completed. □

Theorem 3.3.3

An arbitrary Cayley table of the cyclic group of order 4 differs in at least four places from an arbitrary Cayley table of Klein’s 4-group.

Proof

This has already been shown as part of the revised proof of Theorem 3.3.1. □

The result of Theorem 3.3.1 remains the same if we restrict the class of groups to any one of the following classes of finite groups: (i) soluble groups; (ii) nilpotent groups; (iii) abelian groups; (iv) cyclic groups.

It seems to be natural to raise the following problem:

What is the maximum number of squares which a set of latin squares satisfying the quadrangle criterion and all of the same order n can contain if each pair of squares in the set are to differ from each other in at most m places?

At the beginning of this section, we stated the problem of Fuchs as a problem concerning groups. The analogous result for quasigroups, which was first proved by Dénes and Pásztor(1963), may be deduced as a corollary to the theorem which follows. For this, we need to remember the fact that the multiplication table of an arbitrary quasigroup is a latin square (proved in Theorem 1.1.1).

Theorem 3.3.4

For n = 2 and n ≥ 4 there exist two latin squares of order n which differ in precisely four entries.

Proof

Given two different symbols a and b there are two possible latin squares that can be formed using those symbols, namely,

These two squares are clearly at distance four from each other, settling the case n = 2. Moreover, from Theorem 1.6.3 it follows that for all n ≥ 4 there exists a latin square L_n of order n having a latin subsquare U_n of order 2. Let us form L′ _n from L_n by replacing U_n by the other possible subsquare on the same two symbols. Then d(L_n , L′_n ) = 4 as desired. □

For an analogous result concerning semigroups, see Dénes(1967a).

As regards problem (a) of Fuchs, Frisch(1997) has proved that the Cayley tables of non-isomorphic groups always differ in strictly more than 2n places.

3.4 Incomplete latin squares and partial quasigroups

A latin rectangle of size r × s is called incomplete or partial if less than rs of its cells are occupied. An incomplete or partial latin square is analogously defined. Precisely, we have:

Definition

An n × n incomplete or partial latin square defined on a set S of n symbols is an n × n array such that in some subset of the n ² cells of the array each of the cells is occupied by an element from the set S and such that no element from the set S occurs more than once in any row or column.

In Section 3.2 and Section 3.3, we investigated incomplete latin squares whose elements were not arbitrarily assigned but had been obtained by deleting elements from a given latin square. The example of an incomplete latin square shown in Figure 3.4.2 will make the distinction clear.

In this section we shall consider incomplete latin squares and rectangles more generally and investigate the question of when and whether they can be completed to a latin square or latin rectangle.

Figure 3.4.1 shows an incomplete latin rectangle of size 2 × 4 which cannot be completed to a latin rectangle of the same size. By generalizing, it is easy to see that, for any n ≥ 2, there exists an incomplete latin rectangle with 2n cells occupied which cannot be completed to an n × 2n latin rectangle⁷. On the other hand, Lindner(1970a) proved that an incomplete n × 2n latin rectangle with 2n − 1 cells occupied can always be completed to an n × 2n latin rectangle.

In T.Evans(1960), the following problem was posed:

“What conditions suffice to enable an incomplete n × n latin square to be embeddeded in a fully completed⁸ latin square of order n? In particular, can an n × n incomplete latin square which has n − 1 or less places occupied be completed to a latin square of order n?”

Exactly the same problem was posed by Klarner on page 1167 of Erdös, Rényi and Sös(1970) and independently by Dénes in a lecture given in the late 1960s at the University of Surrey.

It is easy to see that there do exist incomplete latin squares with n cells occupied which cannot be so completed, as Figure 3.4.1 and Figure 3.4.2 illustrate.

The general case of Evans’ problem had not been solved when the first edition ([DK1]) of this book was published but it is now known that his conjecture that any n × n incomplete latin square which has n − 1 or less places occupied can be completed to a latin square of order n is true. Two proofs of this fact are discussed in detail in Chapter 8, Section 10, of [DK2]. We merely remark here that the simplest proof is that of Smetaniuk(1981).

In [DK1], the next pages of this section were devoted to the discussion of partial solutions to Evans’ conjecture and to related embedding problems. Since a much more up-to-date account of this topic is available in [DK2], we refer the reader to that book for more recent results. However, some of the earlier results are not mentioned in [DK2].

Firstly, Marica and Schönheim(1969) proved that an incomplete latin square containing n − 1 arbitrarily chosen elements can be completed to a latin square of order n provided that the chosen elements are in different rows and columns.

Secondly, in Lindner(1970b), that author (using the same technique as Marica and Schönheim) proved that an incomplete latin square containing n − 1 distinct elements can be completed to a latin square of order n provided that the chosen elements are either in different rows or in different columns.

Thirdly, Lindner(1970a) also proved the following theorem: Let L be an n × n incomplete latin square with n − 1 cells occupied. Let r and s denote respectively the number of rows and the number of columns in which occupied cells occur. Then, if r ≤ ⌊n/2⌋ or c ≤ ⌊n/2⌋, L can be completed to a latin square of order n.

In the same connection, one can ask for the solution of the following problem: “How many elements of a latin square of order n and which satisfies the quadrangle criterion can be located arbitrarily subject only to the condition that no row or column shall contain any element more than once?” Since a latin square of odd order which satisfies the quadrangle criterion cannot contain a latin subsquare of order two (see the Corollary to Theorem 1.6.4), it is easy to see that, for n odd, this number is at most three. Thus, for example, no completion of the partial latin square shown in Figure 3.4.3 can satisfy the quadrangle criterion, since it is of odd order.

Moreover, not even two arbitrary elements can be arbitrarily placed in a symmetric latin square of odd order: for Theorem 1.5.4 implies that no element can appear more than once in the main diagonal of such a square.

Csima(1972) has translated Evans’ problem of finding under what conditions a partial latin square can be embedded in a fully completed latin square into a problem about a combinatorial structure which he has called a pattern. For details, the reader is referred to Csima’s paper.

In his paper T.Evans(1960), already referred to, that author posed the following further question: “Can a pair of n × n incomplete latin squares which are orthogonal (insofar as the condition for orthogonality applies to the incomplete squares) be respectively embedded in a pair of t × t orthogonal latin squares; and, if so, what is the smallest value of t for each value of n?” The first part of this question has been answered in the affirmative by Lindner(1976) but the smallest value of t for a given value of n remains unknown so far as the present author is aware.

Somewhat related to this question is an interesting result proved by Lindner(1971b): namely, any finite collection of mutually orthogonal n × n partial latin squares can be embedded in a complete set of mutually orthogonal infinite latin squares.

By an infinite latin square we mean a countably infinite array of rows and columns such that each positive integer occurs exactly once in each row and exactly once in each column. If P is a finite (partial) latin square, we shall denote by C_p the set of all the cells which are occupied in P. If P and Q are finite (partial) latin squares of the same size, we say that P and Q are orthogonal if the cardinalities of the sets C_p ∩ C_q and {(p_ij , q_ij ): (i, j) ∈ C_p ∩ C_q } are equal. If P and Q are infinite latin squares, we say that P and Q are orthogonal provided that the set {(p_ij , q_ij ): (i, j) ∈ C_p ∩ C_q } has the same cardinality as the Cartesian product Z + × Z + si30_e (where Z + si31_e denotes the set of positive integers) and that each pair of cells in different rows and columns is occupied by the same symbol in at most one of P and Q. If {P_i } _i _∈I is a collection of mutually orthogonal latin squares of the same size, we say that this collection is a complete set of mutually orthogonal latin squares provided that each pair of cells in different rows and columns is occupied by the same symbol in exactly one member of the collection. If the latin squares in the collection are finite of order n, the set I has cardinality n − 1, while, if they are infinite, I has cardinality equal to that of the set Z + si32_e .

The reader new to the subject is advised that he will find the above concepts easier to understand if he first reads Section 5.1 and Section 5.2.

For the proof of his result stated above, Lindner used the geometrical concepts of projective plane and partial projective plane. (The connection between orthogonal latin squares and projective planes is explained in Section 5.2.)

Definition

An n × n partial idempotent latin square is an n × n partial latin square with the additional property that, for each i = 1, 2, …, n, the cell (i, i) is either empty or else is occupied by the integer i. An n × n partial symmetric latin square is an n × n partial latin square with the additional property that, if the cell (i, j) is occupied by the symbol k so also is the cell (j, i).

In a series of papers, Lindner solved a number of embedding problems concerning square of these kinds. In particular,

(1) Any finite partial idempotent latin square can be embedded in a finite idempotent latin square [Lindner(1971a)].
(2) Any finite partial symmetric latin square can be embedded in a finite symmetric latin square [Lindner(1972a,1976)].
(3) Any finite partial idempotent and symmetric latin square can be embedded in a finite idempotent and symmetric latin square [Lindner(1972a)].

Subsequently, these results were made more precise and these and other results were proved by more elegant methods by Cruse, Hilton, Lindner and others. A more up-to-date account and more details are given in Sections 4 and 5 of [DK2], chapter 8. Also, in Sections 6 and 7 of that chapter, an account of embedding theorems for partial quasigroups is given.

By a partial quasigroup is meant a half-groupoid G such that, if the equations ax = b and/or ya = b have solutions for x and y in G, then these solutions are unique. A partial loop is a partial quasigroup with an identity element such that the product of this element with each element a of the loop is defined and is equal to a. [By other authors, partial quasigroups have been called incomplete quasigroups or half-quasigroups, see Bruck(1958) and T.Evans(1960).]

In Brandt(1927), that author introduced a special kind of partial groupoid B (which has subsequently been called a Brandt groupoid) satisfying the following postulates:

(1) If any three elements a, b, c satisfy an equation ab = c then each of the three elements is uniquely determined by the other two.
(2) If ab and bc both exist, then (ab)c and a(bc) also exist; if ab and (ab)c both exist, then bc and a(bc) also exist; if bc and a(bc) both exist, then ab and (ab)c also exist; and, in all of these cases, the equation (ab)c = a(bc) is valid and consequently the expression abc has an unambiguous meaning.
(3) To any given element a there corresponds a unique right identity element e such that ae = a, a unique left identity element e′ such that e′a = a and a left inverse ā of a such that āa = e.
(4) If e and e′ are any two members of the set of one-sided identity elements, there exists an element a such that e and e′ are respectively right and left identities with respect to a.

Postulate (1) implies that the multiplication table of a Brandt groupoid is an incomplete latin square and we shall devote the remainder of this section to mentioning some results and conjectures concerning such multiplication tables.

Theorem 3.4.1

The multiplication table of a Brandt groupoid is an incomplete latin square satisfying the quadrangle criterion.

Proof

As we have just remarked, postulate (1) implies that the multiplication table of a Brandt groupoid is an incomplete latin square and it then follows immediately from postulate (2) that the multiplication table of a Brandt groupoid satisfies the quadrangle criterion. □

We should like to point out by means of an example that incomplete latin squares exist which satisfy the quadrangle criterion but which can be completed to latin squares in which the quadrangle criterion does not hold. The incomplete latin square exhibited in the left-hand square of Figure 3.4.4 has these properties, as is indicated by the right-hand square.

On the other hand, the authors conjecture that every Brandt groupoid can be embedded in a quasigroup Q which is group isotopic. The conjecture is certainly valid, for example, for the Brandt groupoid (B, ο) given as follows.

The elements of (B, ο) are all binary triplets and we shall denote them as follows:

1 = ( 000 ) 2 = ( 100 ) 3 = ( 010 ) 4 = ( 110 ) 5 = ( 001 ) 6 = ( 011 ) 7 = ( 101 ) 8 = ( 111 )

si33_e

If (H, +) denotes the cyclic group of order two with elements 0, 1, the product of two triplets (a b c) and (d e f) is defined to be the triplet (a b + e f) if c = d and is not defined otherwise.

Then Figure 3.4.5 shows that the multiplication table of (B, ο) can be embedded in the multiplication table of a quasigroup Q which is isotopic to the generalized Klein group of order 8. (In the diagram, the products which are defined in (B, ο) are enclosed in squares.)

Let us remark that it is well-known that an arbitrary Brandt groupoid B can be embedded in a semigroup S with one additional element 0 such that a0 = 0a = 00 = 0 for all a ∈ B and such that ab = 0 in S if a, b are in B and ab is not defined in B. [See, for example, page 35 of Bruck(1958).] This fact leads the authors of this book to propose the alternative conjecture that in fact any Brandt groupoid can be embedded in a group.

3.5 Partial transversals and generalized transversals

As has been shown earlier, many latin squares do not have any transversals. For example, see Theorem 2.5.1 and Theorem 2.5.4. This fact led Koksma(1969) to ask “What is the largest number of cells of an arbitrarily chosen latin square (or rectangle) of given order which can be contained in a single partial transversal?”

Definition

By a partial transversal of a latin square or rectangle is meant a collection of cells taken from different rows and different columns and containing different entries. The number of cells in the collection is called the length of the partial transversal.

Koksma proved that an arbitrary latin square of order n (n ≥ 7) has at least one partial transversal of length t ≥ (2n + 1)/3. We outlined his proof in [DK1]. However, this lower bound has subsequently been much improved. An account of more recent work on the question up to 1990 has been given in [DK2] so we shall not repeat it here. However, so far as the present author is aware, the best lower bounds for t so far obtained are those in Hatami and Shor(2008) and Fu, Lim and Fu(2002) which both give bounds of the form t ≥ n − O(log n)².

Of course, neither of these bounds is anywhere near the bound t ≥ n − 1 conjectured by Brualdi (see Section 1.5) and independently by Stein(1975) nor to the bound t = n for latin squares of odd order conjectured by Ryser. However, in Wanless and Webb(2006), evidence is offered to suggest that the latter conjecture may be false: namely, these authors have proved that, for every order n > 3, there exists a latin square which contains a cell that is not included in any transversal. [In fact, stronger results have been obtained. See Egan and Wanless(2012) or page 408 of Wanless(2011).] For even order, this result was shown by the corollary to Theorem 2.5.4. It follows that, for every order n > 3, there exist latin squares with no orthogonal mate. [See Section 5.1 for the definition of this concept. Such squares were called bachelor squares by Van Rees(1990).] Because the proof (for squares of odd order) is short and elegant, we give it here.

Before doing so, it is useful to have the following definition.

Definition

In a latin square of order n, a collection of n cells, one from each row and one from each column is called a chain. The entries in the cells of a chain are its elements and the number of these which are distinct is the rank of the chain.9

The number of chains of rank i in a particular latin square L is denoted by t_i .

Lemma

Let L be a latin square of order n with rows and columns indexed by the set Z n + = { 0 , 1 , … , n − 1 } si34_e and with symbols also from Z n + si35_e . Let s denote the symbol in row r and column c and let T be a transversal of L. Then ∑ ( r , c , s ) ∈ T ( r + c − s ) ≡ 0 si36_e or n/2 mod n according as n is odd or even.¹⁰

Theorem 3.5.1

For every odd order n = 2m + 1, there exists a latin square which contains a cell that is not contained in any transversal.

Proof

By definition of a transversal, each symbol of Z n + si37_e occurs once in each of ∑r, ∑c and ∑s and so

∑ ( r , c , s ) ∈ T ( r + c − s ) = ( n − 1 ) n / 2 = m ( 2 m + 1 ) ≡ 0 if n = 2 m + 1 or = ( 2 m − 1 ) m ≡ n / 2 if n = 2 m .

si38_e

□

Let us now consider the latin square L = (l_ij ) which is a slight modification of the cyclic latin square of order n = 2m + 1 and is defined as follows:

l ij = { 1 if ( i , j ) = ( 0 , 0 ) or ( 1 , n − 1 ) 0 if ( i , j ) = ( 1 , 0 ) or ( 2 , n − 1 ) j + 2 if i = 0 and j = { 1 , 3 , 5 , … , n − 2 } j if i = 2 and j = { 1 , 3 , 5 , … , n − 2 } i + j otherwise

si39_e

Then the entry 0 in the cell (1, 0) is not in any transversal because r + c − s = 1 for this cell while r + c − s = −2 for each of the modified cells in row 0 except the cell (0,0) and r + c − s = 2 for each of the modified cells in row 2 while r + c − s = 0 for all other cells and so ∑(r + c − s) = 0 is impossible if the summation is over the cells of a chain. □

We exhibit this modified cyclic square in the left hand square of Figure 3.5.1 for the case n = 7.

In fact, four different proofs of the above result exist. The above proof is taken from Egan(2011). Alternative proofs are in A.B.Evans(2006), Wanless and Webb(2006), Egan and Wanless(2012).

If the entries in the cells of a chain are all different, we have a transversal. If not, the cells whose entries are all different form a partial transversal as defined above.

It has been shown in Cameron and Wanless(2005) that every latin square possesses a chain in which no symbol occurs more than twice.

Another question which we may ask is “What is the shortest length of a non-extendible partial transversal?” (The longest length of such a partial transversal is covered by the conjectures of Brualdi-Stein and Ryser.)

The shortest length is not less than n/2 because otherwise there would not be sufficient symbols used in the partial transversal to fill the subsquare formed by the rows and columns not containing cells of the partial transversal. On the other hand, for all n > 4, non-extendible partial transversals of length ⌈n/2⌉ do exist since latin squares of order n which contain a subsquare S of order ⌊n/2⌋ and a partial transversal containing the symbols of S but not involving any of the rows and columns of S can easily be constructed. See the right hand square of Figure 3.5.1 for an example. These observations are in Wanless(2011).

In contrast to this result, Cavenagh, Hämäläinen and Nelson(2009) have proved that, for any prime p, every partial transversal of length 3 in the Cayley table of the cyclic group of order p can be extended to a transversal of length p.

In [DK2], we discussed several generalizations of the concept of a transversal. Of these, the one which has been investigated most fully in recent years is the k-plex.

Definition

A k-plex in a latin square of order n is a set of nk cells, k from each row, k from each column and including k occurrences of each symbol. When convenient, we shall call such a k-plex a plex of order k.

Such objects for the case k = 2 were first studied by Finney(1945) and Freeman(1985) who called them duplexes (from which epithet came the name k-plex when the concept was generalized). Duplexes have statistical applications because, for example, although the cells of a 6 × 6 cyclic latin square cannot be partitioned into six disjoint transversals, they can be partitioned into three disjoint duplexes.

A conjecture which has been attributed to Rodney [see Vaughan-Lee and Wanless(2003)] is that every latin square contains a duplex. It follows from the truth of the Hall-Paige conjecture that Rodney’s conjecture is true for all group-based latin squares, as is shown in Vaughan-Lee and Wanless(2003). In Wanless(2002), that author has shown that, for latin squares based on soluble groups, a more general result is true: namely, that such squares have a 2c-plex for each possible integer c. He has obtained several other related results in the same paper.

We note that the entries not in a k-plex of a latin square form an (n − k)-plex. More generally, it may be possible to partition the cells of a latin square L of order n into a set of plexes of orders k ₁, k ₂, …, k _s, where ∑ i = 1 s k i = n si40_e . When this is possible, we shall say that L has a (k ₁, k ₂, …, k_s )-plex partition. Of particular interest is the case when all the plexes have the same order k (necessarily a divisor of n). For example, the cyclic latin square Z ₆ of order 6 is the union of three duplexes as shown in the left-hand square of Figure 3.5.2. Thus, Z ₆ has a duplex partition. More generally, we shall call a (k, k, …, k)-partition a k-plex partition. For example, the right-hand square of Figure 3.5.2, given in Wanless(2011), has a 3-plex partition. In particular, if L has a 1-plex partition, then it has an orthogonal mate. (See Section 5.1 for the latter concept.)

The union of an h-plex and an l-plex is an (h + l)-plex. However, it is not always possible to split an (h + l)-plex into an h-plex and an l-plex. If a k-plex contains no h-plex for 0 < h < k, we say that it is indivisible. For example, since the cyclic latin square of order six has no transversals (that is, no 1-plexes), then clearly the duplexes shown in Figure 3.5.2 are indivisible.

It has been shown that, for every k ≥ 2 and m ≥ 2, there exists a latin square of order mk with an indivisible k-plex partition. Also, if n = 2k + 1 ≥ 5, there is a latin square of order n with an indivisible (k, k, 1)-plex partition and an indivisible (k, k + 1)-partition. See Bryant, Egan, Maenhaut and Wanless(2009) and Egan and Wanless(2011) for the details.

As regards the question “For which integers k and n is there a latin square of order n which contains an indivisible k-plex?”, it has been shown in the first of the two papers just cited that, if 5k ≤ n, such an indivisible k-plex always exists.

The reader will have observed that, in each of the first three chapters of this book, we have devoted whole sections to the topic of transversals and their generalizations. (We discuss their enumeration in Chapter 4 and they also play a prominent role in [DK2].) It would be easy to devote our whole book to this topic. Instead, we refer the reader to Chapters 2, 3 and 6 of [DK2] and to a recent survey paper by Wanless(2011) which we have already cited several times.