Chapter 4 Introduction

This thesis is about latin squares. More specifically, this thesis is about problems of embedding latin rectangles and completing partial latin squares. The aims of this introduction are, firstly, to provide the reader with the background needed to follow later chapters, secondly, to give motivation for solving the problems which are tackled in this thesis and, thirdly, to give a description of which problems have been solved and which remain open conjectures.

The most familiar definition of a latin square, although by no means the only one possible, is of a square array which has the latin property.

Definition 4.1 An \(r\times s\) array \(A\) on \(\Sigma\) has the latin property if and only if, for all \((i,k)\in [r]^2\) and \((j,l)\in [s]^2\) if \((i,j)\) and \((k,l)\) are both filled cells of \(A\) then \(A(i,j)=A(k,l)\) implies that either \(i\neq k\) and \(j\neq l\) or \(i=k\) and \(j=l\).

Definition 4.2 A latin square of order on is a complete \(n\times n\) array on \(\Sigma\), which has the latin property. A latin square of order is a pair \((\Sigma,L)\), where \(L\) is a latin square of order \(n\) on \(\Sigma\).

In this thesis, for the most part, \(\Sigma=[n]\). So those latin squares on \([n]\) are given a special name.

Definition 4.3 A natural latin square of order is a latin square of order \(n\) on \([n]\).

\[\begin{equation} \left[ \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{array} \right] \end{equation}\]

Choosing to single out the latin squares on \([n]\) is purely a convention. Indeed, in the setting in which latin squares arise most naturally, as the multiplication tables of groups, \(\Sigma\) is the set of elements of a group.

Historically, latin squares go back at least to Euler but it was Cayley who first observed them in their algebraic setting.

Definition 4.4 The multiplication table of a group \((G,\cdot)\) of order \(n\) is the \(|G|\times |G|\) array \(M\) on \(G\) with rows and columns indexed by \(G\) for which \(M(g,h)=g\cdot h\) for every \((g,h)\in G\times G\)

Cayley observed that the multiplication table of a group is a latin square of order \(|G|\) on \(G\). The converse, that every latin square is the multiplication table of some group, is not true. It turns out that a certain type of non-associative groupoid known as a quasigroup is the precise algebraic analogue of the latin square.

Definition 4.5 A quasigroup \((Q,\cdot)\) is a groupoid with the property that, for all \(a,b\in Q\), the equations \(a\cdot x=b\) and \(y\cdot a=b\) are uniquely solvable for \(x,y\in Q\)

A long-standing and, in general, unsolved problem about quasigroups is the quasigroup completion problem (QCP) which asks for necessary and sufficient conditions for the existence of a quasigroup \(Q\) which satisfies certain prescribed identities of the form \(a\cdot b=c\) for \(a,b,c\in Q\). In terms of latin squares this is akin to asking for necessary and sufficient conditions for a latin square \(A\) of order \(|Q|\) on \(Q\) such that \(A(a,b)=c\) if \(a\cdot b=c\) is an identity. For instance, is there a Latin square of order 5 on \([5]\) which can be obtained from the array in (4.1) by replacing each dash by one symbol from the set \([5]\)?

\[\begin{equation} \left[ \begin{array}{ccccc} 1 & 2 & 3 & 4 & - \\ 2 & - & - & 1 & - \\ 3 & - & 4 & 5 & 2 \\ - & 3 & - & 2 & - \\ 4 & 5 & - & - & - \end{array} \right] \tag{4.1} \end{equation}\]

It is not too difficult to find a solution. One solution is shown in (4.2). In fact, in this case, it is just as easy to see that the solution also happens to be unique. In general, however, the answer to this question is far from obvious. A trivial necessary condition for the existence of a solution is that there be no row or column containing a repeated symbol. For this reason, attention is immediately confined to partial latin squares.

\[\begin{equation} \left[ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 5 & 1 & 3 \\ 3 & 1 & 4 & 5 & 2 \\ 5 & 3 & 1 & 2 & 4 \\ 4 & 5 & 2 & 3 & 1 \end{array} \right] \tag{4.2} \end{equation}\]

Definition 4.6 A partial latin square of order on \(\Sigma\) is an \(n\times n\) array with the latin property, every cell of which is either empty or contains an element of \(\Sigma\). A partial latin square of order \(n\) on \(\Sigma\) is natural if and only if \(\Sigma\subseteq [n]\).

The term partial latin square can be misleading. It might suggest to some that every partial latin square can be completed to give a latin square. This is a long way from the truth. In fact the central problem surrounding partial latin squares is to find necessary and sufficient conditions for a partial latin square to be completable to a latin square.

Beyond the problem of characterising completable partial latin squares there is the closely related problem of embedding partial latin squares. If a given partial latin square is incompletable there may still be hope that it can be embedded in some larger latin square. Another central problem about partial latin squares is to determine whether a given partial latin square can be finitely embedded and if it can be finitely embedded then in how small a latin square it can be embedded.

Definition 4.7 If \(A\) is an \(r\times s\) array on \(\Sigma\) and \(B\) is an \(n\times n\) array on \(\Sigma'\) then \(A\) is embedded in \(B\) if and only if \(B(i,j)=A(i,j)\) for every filled cell \((i,j)\) of \(A\).

Definition 4.8 A partial latin square of order \(n\) on \(\Sigma\) is completable if and only if \(A\) can be embedded in a latin square of order \(n\) on \(\Sigma\).

The latin square in (4.2) proves that the partial latin square of (4.1) is completable.

In its most general form the quasigroup completion problem, in the language of latin squares, asks for necessary and sufficient conditions for a partial latin square to be completable. This has proved to be a difficult question to answer. There have been at least two different approaches to tackling this problem. One approach is to consider what happens when only a small number of cells are prescribed. In this area the solution of the Evans Conjecture, discussed in Section 1, by Smetaniuk (1981) and, independently, by thankevans is the most remarkable result.

Another approach is to consider the embedding of latin rectangles. In this line the most important results, introduced in Section 2, are due to Ryser (1951), Hall (1945) and Evans (1960).

For the remainder of this introduction these results are described and it is shown how the problems considered in this thesis arise naturally from them.

References

Smetaniuk, B. 1981. “A New Construction on Latin Squares - I: A Proof of the Evans Conjecture.” Ars Combinatoria, no. 9: 155–72.

Ryser, H. J. 1951. “A Combinatorial Theorem with an Application to Latin Rectangles.” Proc. Amer. Math. Soc., no. 2: 550–52.

Hall, M. 1945. “An Existence Theorem for Latin Squares.” Bull. Amer. Math. Soc. 51: 387–88.

Evans, T. 1960. “Embedding Incomplete Latin Rectangles.” Amer. Math. Monthly 67: 958–61.