Chapter 1 The Evans Conjecture

1.1 The Evans Conjecture

At first it might be expected that the question of whether a partial latin square is completable or not is purely a question of the number of prescribed cells. Certainly if a particular latin square is incompletable then it cannot become completable by prescribing more cells. Any completion of the modified square would have been a completion or the original square.

However, it is not true that all latin squares of a given order with the same number of prescribed cells are equally likely to be completable. For instance there are, obviously, completable latin squares of order $n$ with $n$ prescribed cells and yet, conversely, it is not too dificult to construct incompletable latin squares of order $n$ which have just $n$ prescribed cells. \tag{1.1} shows an incompletable partial latin square of order 2 with 2 prescribed cells.

\[\begin{equation} \left[ \begin{array}{cc} 1 & - \\ - & 2 \end{array} \right] \tag{1.1} \end{equation}\]

There are several reasons why the partial latin square in Figure \[fig120\] is incompletable and in every case the reason gives rise to a construction which can be generalised to give incompletable partial latin squares of all orders $n>1$ with $n$ prescribed cells. A natural question to ask is : what is the greatest $k$ such that every latin square of order $n$ with at most $k$ prescribed symbols is completable? Figure \tag{1.1} implies $k<n$. In 1960, Evans conjectured that $k=n-1$. This was proved by Smetaniuk Smetaniuk (1981) and, independently, by Andersen and Hilton Andersen and Hilton (1983).

Theorem 1.1 Evans Conjecture A partial latin square of order $n$ with at most $n-1$ prescribed cells is completable.

In fact Andersen and Hilton went further and gave a characterisation Andersen and Hilton (1983) of incompletable latin squares of order $n$ with $n$ prescribed cells. Later Andersen Andersen (1985) went further still and extended this characterisation to squares with $n+1$ prescribed cells.

To describe the theorem of Andersen and Hilton three different constructions for incompletable natural partial latin squares of order $n$ with $n$ prescribed cells are introduced in Definitions \[def140\]-\[def180\]. Each of these constructions is a generalisation of Figure \[fig120\]. The first construction is obtained by observing that in Figure \[fig120\] there is an empty cell $(i,j)$, either $(1,2)$ or $(2,1)$ in Figure \[fig120\], with the property that all symbols in $[n]$ lie either in the $i$th row or $j$th column. The partial latin square is incompletable because there is no symbol which can be placed in $(i,j)$ without violating the latin property.

Definition 1.1 A partial latin square $A$ of order $n$ with $n$ prescribed cells is Type 1 if and only if, for some $k\in [n]$, $A(1,j)=j$ for all $j\in [k]$ and $A(k+1,i)=k+i-1$ for all $i\in [n]\backslash [k]$.

\[\begin{equation} \left[ \begin{array}{cccccc} 1 & 2 & \cdots & k & & \\ & & & & k+1 & \\ & & & & k+2 & \\ & & & & \vdots & \\ & & & & n & \\ & & & & & \end{array} \right] \tag{1.2} \end{equation}\]

A Type 1 partial latin square is incompletable because there is no symbol which can be placed in cell $(1,k+1)$ without violating the latin property. Another reason that a partial latin square of Type 1 is incompletable is the existence of an “incompletable symbol”. In a natural latin square of order $n$ every symbol in $[n]$ occurs exactly once in every row and every column. If $P$ is a natural partial latin square then a symbol $k\in [n]$ is completable if and only if $P$ can be embedded in a partial latin square of order $n$ which has $n$ cells containing $k$. In a Type 1 partial latin square no symbol can be placed in cell $(1,k+1)$ without violating the latin property, therefore at least one symbol in $[n]$ is incompletable.

As in a completable partial latin square every symbol must be completable so must every row and every column. If $Q$ is a row or column of a partial latin square $P$ of order $n$ then $Q$ is completable if and only if $P$ can be embedded in a partial latin square of order $n$ in which row/column $Q$ has no empty cells. Figure \[fig120\] is also incompletable because both of its rows and both of its columns are incompletable.

Definition 1.2 \[def160\] A partial latin square $A$ of order $n$ with $n$ prescribed cells is Type 2 if and only if, for some $k\in [n]$, $A(1,j)=j$ for all $k\in [k]$ and $A(j-k+1,j)=k+1$ for all $j\in [n]\backslash [k]$.

A Type 2 partial latin square is incompletable because the first row is incompletable. Figure \[fig170\] illustrates Type 2 partial latin squares.

\[\left[ \begin{array}{cccccccc} 1 & 2 & \cdots & k & & & &\\ & & & & k+1 & & &\\ & & & & & k+1 & &\\ & & & & & & \ddots &\\ & & & & & & & k+1\\ & & & & & & &\\ & & & & & & &\\ & & & & & & & \end{array} \right]\]

Definition 1.3 \[def180\] A partial latin square $A$ of order $n$ with $n$ prescribed cells is Type 3 if and only if, for some $k\in [n]$, $A(i,1)=i$ for all $i\in [k]$ and $A(i,i-k+1)=k+1$ for all $i\in [n]\backslash [k]$.

A Type 3 partial latin square is incompletable because the first column is incompletable. Figure \[fig190\] illustrates Type 3 partial latin squares.

\[\left[ \begin{array}{cccccccc} 1 & & & & & & &\\ 2 & & & & & & &\\ \vdots & & & & & & &\\ k & & & & & & &\\ & k+1 & & & & & &\\ & & k+1 & & & & &\\ & & & \ddots & & & & \\ & & & & k+1 & & & \end{array} \right]\]

Andersen and Hilton Andersen and Hilton (1983) showed that these three types of incompletable latin square are, essentially, the only incompletable partial latin squares of order $n$ with $n$ prescribed cells. Any partial latin square which can be obtained from one of these types by relabelling the elements consistently or by swapping rows and columns around is also obviously incompletable. This notion is made precise by the concept of isotopic latin squares.

Definition 1.4 If $A$ is an array of order $n$ on $S$ and $B$ is an array of order $n$ on $T$ then $A$ and $B$ are isotopic if and only if there is a triple $(\theta,\psi,\phi)$ of bijections $\theta,\psi:[n]\rightarrow [n]$, $\phi:S\rightarrow T$ such that $A(i,j)=\phi(B(\theta(i),\psi(j)))$ for all $i,j\in [n]$. Such a triple is called an isotopy of $B$ onto $A$ and $A$ and $B$ are said to be isotopes of one another.

Example 1.1 The natural latin squares $A$ and $B$ in Figure \[fig1975\] are isotopic by the isotopy

$ (( \[\begin{array}{ccc} 1 & 2 & 3 \\ 2 & 1 & 3 \end{array}\] ), ( \[\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 3 & 2 \end{array}\] ), ( \[\begin{array}{ccc} 1 & 2 & 3 \\ 1 & 2 & 3 \end{array}\]

) ) $

of $A$ onto $B$. In other words the latin square on the right can be obtained from the latin square on the left by swapping rows 1 and 2, columns 2 and 3 and leaving symbols unchanged.

$A=\left[ $B=\	left[ \begin{array}{ccc}
\begin{array}{ccc}	2 & 1 & 3 \
1 & 2 & 3 \	1 & 3 & 2 \
2 & 3 & 1 \	3 & 2 & 1
3 & 1 & 2	\end{array}]$
\end{array}
]
$

\[fig1975\]

Definition 1.5 A bad partial latin square of order with prescribed cells is a partial latin square of order $n$ which is isotopic to a partial latin square of Type 1, Type 2 or Type 3.

Theorem 1.2 \[Andersen and Hilton @thankevans\] \[thm200\] A partial latin square of order $n$ with $n$ prescribed cells is either bad or completable.

In Damerell (1983) Damerell proved Theorem \[thm200\] by adapting the approach of Smetaniuk.

There is a even nicer way of presenting Theorem \[thm200\] which uses the idea of conjugate latin squares. The conjugates of a partial latin square $A$, possibly a latin square, are the $3!=6$ elements of $\{A^g\,|\,g\in G\}$, where $G$ is the group of permutations of $\{i,j,k\}$ and, for all $g\in G$, $A^g$ is defined by $A^g(i,j)=k$ if and only if $A(g^{-1}(i),g^{-1}(j))=g^{-1}(k)$ and $A^g(i,j)$ is empty if and only if $A(g^{-1}(i),g^{-1}(j))$ is empty. Figure \[fig220\] shows a latin square and its six conjugates.

\[A=A^{(ij)}=\left[ \begin{array}{ccc} 1 & 2 & 3\\ 2 & 3 & 1\\ 3 & 1 & 2 \end{array} \right]\]

\[A^{(ik)}=A^{(ijk)}=\left[ \begin{array}{ccc} 1 & 3 & 2\\ 2 & 1 & 3\\ 3 & 2 & 1 \end{array} \right]\]

\[A^{(jk)}=A^{(ikj)}=\left[ \begin{array}{ccc} 1 & 2 & 3\\ 3 & 1 & 2\\ 2 & 3 & 1 \end{array} \right]\]

It can be shown that if $A$ is a Type 1 partial latin square then $A^{(jk)}$ is a Type 2 partial latin square and $A^{(ijk)}$ is a Type 3 partial latin square. It can also be shown that a partial latin square is completable if and only if all its conjugates are completable. It follows that Theorem \[thm200\] holds even if the definition of bad is modified so that a bad partial latin square is a partial latin square which is a conjugate of some partial latin square isotopic to a Type 1 partial latin square. In essence, Theorem \[thm200\] says that all but a single class of partial latin squares of order $n$ with $n$ prescribed symbols, namely the isotopes of the conjugates of a Type 1 partial latin square, are completable.

In Andersen (1985) Theorem \[thm200\] was strengthend by Andersen to give all incompletable partial latin squares of order $n$ with at most $n+1$ prescribed cells. When exactly $n+1$ cells are prescribed there are thirteen incompletable types, ten of which are illustrated in Figure \[fig210\] and described in Definition \[def202\].

\[def202\] A partial latin square of order $n$ is Type

if and only if $n\geq 3$, $L(1,i)=i$ for all $i\in [n-3]$, $L(2,n-2)=L(3,n-1)=n-2$ and $L(3,n-2)=L(2,n-1)=n-1$, Type
if and only if $n\geq 3$, $L(i,1)=i$ for all $i\in [n-3]$, $L(n-2,2)=L(n-1,3)=n-2$ and $L(n-2,3)=L(n-1,2)=n-1$, Type
if and only if $n\geq 3$, $L(i,i)=i$ for all $i\in [n-3]$, $L(n-2,n-2)=L(n-1,n-1)=2$ and $L(n-2,n-1)=L(n-1,n-2)=3$, Type
if and only if $n\geq 4$, $L(1,i)=i$ for all $i\in [n-3]$, $L(2,n-2)=L(3,n-1)=n-2$ and $L(2,n-1)=L(4,n-2)=n-1$, Type
if and only if $n\geq 4$, $L(i,1)=i$ for all $i\in [n-3]$, $L(n-2,2)=L(n-2,3)=n-2$ and $L(n-1,2)=L(n-2,4)=n-1$, Type
if and only if $n\geq 4$, $L(i,i)=i$ for all $i\in [n-3]$, $L(n-2,n-2)=L(n-1,n-1)=2$, $L(n-2,n-1)=3$ and $L(n-1,n-2)=4$, Type
if and only if $n\geq 5$, $L(1,i)=i$ for all $i\in [n-3]$, $L(2,n-2)=L(3,n-1)=2$, and $L(4,n-2)=L(5,n-1)=n-1$, Type
if and only if $n\geq 5$, $L(1,i)=i$ for all $i\in [n-3]$, $L(n-2,2)=L(n-1,3)=n-2$, and $L(n-2,4)=L(n-1,5)=n-1$, Type
if and only if $n\geq 5$, $L(i,i)=1$ for all $i\in [n-2]$, $L(n-2,n-2)=2$, $L(n-2,n-1)=3$, $L(n-1,n-2)=4$ and $L(n-1,n-1)=5$, and Type
if and only if $n=4$, $L(1,1)=L(2,2)=1$, $L(3,3)=3$, $L(4,4)=4$.

The remaining three incompletable types are those which can be obtained from a bad partial latin square with $n$ prescribed symbols by filling an empty cell.

\[def203\] If $A$ is an $n\times n$ array and $e=(\alpha,\beta)\in [n]^2$, is a filled cell of $A$ then $A^\star=A^{\star(e)}$ is the $n\times n$ array defined by $A^\star(i,j)=A(i,j)$ for all $(i,j)\in [n]^2$ if and only if $A(i,j)$ is filled and $(i,j)\neq e$ and $A^\star(i,j)$ is empty if and only if $A(i,j)$ is empty or $(i,j)=e$.

In other words $A^{\star(e)}$ is obtained from $A$ by removing the element in cell $e$.

\[def204\] A bad partial latin square of order with prescribed cells is a partial latin square $A$ of order $n$ which is either isotopic to a partial latin square of Type $k$ for some $k\in [13]\backslash [3]$ or has a cell $(i,j)$ such that $A^{\star(i,j)}$ is a bad partial latin square of order $n$ with $n$ prescribed cells.

With this extended definition, Theorem \[thm205\] holds.

\[Andersen @LDA3\] \[thm205\] A partial latin square of order $n$ with at most $n+1$ prescribed cells is either bad or completable.

In Section \[sec230\] an analogue of Theorem \[thm200\], also due to Andersen and Hilton, for symmetric latin squares is presented.

1.2 The Symmetric Evans Conjecture

Every new result in this thesis is, essentially, a result about symmetric latin squares (although the result of Chapter 2 seems more suited to being presented as a result about edge-coloured graphs). In this section another result of Andersen and Hilton, which is the analogue of Theorem \[thm200\] for symmetric latin squares, is presented.

\[def240\] An $r\times s$ array $A$ is symmetric if and only if $A(i,j)=A(j,i)$ for all filled cells $(i,j)$ of $A$ and $A(i,j)$ is empty if and only if $A(j,i)$ is empty.

\[def250\] A symmetric partial latin square $A$ of order $n$ on $\Sigma$ is completable if and only if $A$ can be embedded in some symmetric latin square of order $n$ on $\Sigma$.

The Evans Conjecture asks how many cells can be prescribed so that all partial latin squares with that number of prescribed cells are completable. The answer is $n-1$. When it comes to symmetric latin squares it is no longer true that as many as $n-1$ cells can be prescribed unconditionally. For example, Figure \[fig260\] shows two incompletable natural partial latin squares of order $n$ with $n-1$ prescribed cells.

$	$
\left[	\left[
\begin{array}{ccc	} \begin{array}{cccc}
1 & - & - \	1 & - & - & - \
- & 1 & - \	- & 2 & - & - \
- & - & -	- & - & 3 & - \
\end{array}	- & - & - & -
]	\end{array}
$	]
$

The symmetric partial latin squares in Figure \[fig260\] are incompletable because their main diagonals are inadmissible.

\[def270\] A diagonal in an $n\times n$ array $A$ is a set of $n$ cells, no two of which belong to the same row or column of $A$. The main diagonal of $A$ is the set $\{(i,i)\,|\, i\in [n]\}$.

The key point here is that in a symmetric latin square, precisely because of the symmetry, every symbol $\sigma$ occurs an even number of times in cells outside of the main diagonal. Therefore, as every symbol $\sigma$ occurs $n$ times in total it follows that the number of cells of the main diagonal containing symbol $\sigma$ is congruent to $n$ modulo 2. The partial latin squares in Figure \[fig260\] are incompletable because there are more symbols which occur on the main diagonal a number of times (zero included) incongruent to $n$ modulo 2 than there are empty cells on the main diagonal. Therefore these partial latin squares can only be embedded in arrays of order $n$ which have at least one symbol $\sigma$ which occurs a number of times on the main diagonal incongruent to $n$ modulo 2. Hence they cannot be embedded in a symmetric natural latin square of order $n$.

\[def275\] If $A$ is an $n\times n$ array on $\Sigma$ then $\bf{D(A,\sigma)}=\{(i,i)\,|\, i\in [n]\mbox{ and }A(i,i)=\sigma\}$ and $\bf{d(A,\sigma)}=|D(A,\sigma)|$. Also, $D(A)=D(A,\Sigma)=\cup_{\sigma\in\Sigma}D(A.\sigma)$ and $d(A)=|D(A)|$.

\[lem280\] If $A$ is a symmetric latin square of order $n$ on $\Sigma$ then $d(A,\sigma)\equiv n\bmod 2$, for all $\sigma\in\Sigma$.

Let $A$ be a symmetric latin square of order $n$ on $\Sigma$. Let $L(\sigma)=\{(i,j)\,|\,1\leq i<j\leq n\mbox{ and } A(i,j)=\sigma\}$ and $G(k)=\{(i,j)\,|\, 1\leq j<i\leq n\mbox{ and } A(i,j)=\sigma, \}$ for all $\sigma\in\Sigma$. In other words, $L(\sigma)$ is the set of cells above the main diagonal containing $\sigma$ and $G(\sigma)$ the set of cells below the main diagonal containing $\sigma$. Let $l(\sigma)=|L(\sigma)|$ and $g(\sigma)=|G(\sigma)|$ for all $\sigma\in\Sigma$. Then $l(\sigma)+d(A,\sigma)+g(\sigma)=n$ because every cell containing $\sigma$ appears exactly once in $L(\sigma)\cup D(A,\sigma)\cup G(\sigma)$ and there are $n$ cells containing $\sigma$ in $A$. Now, because $A$ is symmetric $(i,j)\leftrightarrow (j,i)$ is a bijection between $L(\sigma)$ and $G(\sigma)$. Therefore $l(\sigma)+g(\sigma)$ is even and hence $d(A,\sigma)\equiv n\bmod 2$.

An almost immediate corollary is Lemma \[lem290\] which says that if $n$ is odd then a symmetric latin square of order $n$ has a main diagonal in which every symbol occurs exactly once.¹

\[lem290\] If $A$ is a symmetric latin square of odd order $n$ on $\Sigma$ then $d(A,\sigma)=1$ for all $\sigma\in\Sigma$.

Let $A$ be a symmetric latin square of odd order $n$ on $\Sigma$. By Lemma \[lem280\] $d(A,\sigma)$ is odd for all $\sigma\in\Sigma$. Therefore, as zero is even, $d(A,\sigma)\geq 1$ for all $\sigma\in\Sigma$. Suppose there exists some $\sigma\in\Sigma$ with $d(A,\sigma)>1$. Then, as the main diagonal contains $n$ cells, there exists $\sigma'\in\Sigma$, $\sigma'\neq\sigma$, such that $d(A,\sigma')<1$. Therefore $d(A,\sigma')=0\equiv n+1\bmod{2}$. Hence, by Lemma \[lem280\], there is no such $\sigma$, and so $d(A,\sigma)=1$ for all $\sigma\in\Sigma$.

Trivially, a completable symmetric partial latin square has a main diagonal with the property that its empty cells can be filled to give the main diagonal of some symmetric latin square.

\[def292\] A partial latin square $A$ has an admissible complete main diagonal $D$ if and only if $D$ has no empty cells and $d(A,\sigma)\equiv n\bmod 2$ for all $\sigma\in\Sigma$.

\[def293\] If $A$ is a symmetric partial latin square of order $n$ on $\Sigma$ then $A$ has a completable main diagonal if and only if $A$ can be embedded in a symmetric partial latin square $B$ of order $n$ on $\Sigma$ with an admissible complete main diagonal.

Trivially, a completable symmetric partial latin square has a completable main diagonal. The question is, which partial latin squares have completable main diagonals? The answer is: those with as many empty cells on the main diagonal as there are symbols $\sigma\in\Sigma$ for which $d(A,\sigma)\equiv (n+1)\bmod 2$, although this is, by no means, obvious.

\[def295\] If $A$ is an $n\times n$ array on $\Sigma$ then $O(A)=\{\sigma\in\Sigma\,|\,d(A,\sigma)\equiv (n+1)\bmod 2\}$ and $o(A)=|O(A)|$.

\[def300\] The main diagonal of a symmetric partial latin square $A$ of order $n$ is an admissible main diagonal if and only if $|O(A)|\leq n-d(A)$.

\[lem310\] The main diagonal $D$ of a symmetric partial latin square is completable only if $D$ is admissible.

Let $A$ be a symmetric partial latin square of order $n$ on $\Sigma$ with main diagonal $D$. If $D$ is completable then, by definition, $A$ can be embedded in a partial latin square $B$ of order $n$ on $\Sigma$ with an admissible complete main diagonal $E$. As $D(B,\sigma)\equiv n\bmod 2$ for all $\sigma\in\Sigma$ it follows that $D(B,\sigma)-D(A,\sigma)$ is odd if and only if $D(A,\sigma)\equiv (n+1)\bmod 2$. Therefore, if $D(A,\sigma)\equiv (n+1)\bmod 2$ it follows that $D(B,\sigma)-D(A,\sigma)>0$ and hence $D(B,\Sigma)-D(A,\Sigma)\geq O(A)$. Now the result follows because $d(A,\Sigma)=d(A)$ by definition and $D(B,\Sigma)=n$ because there are $n$ filled cells in $E$.

\[def330\] A symmetric partial latin square $P$ is an admissible symmetric partial latin square if and only the main diagonal of $P$ is admissible.

\[lem320\] A completable symmetric partial latin square is admissible.

Be definition, a symmetric partial latin square $P$ of order $n$ is completable if and only if $P$ can be embedded in a symmetric latin square $L$ of order $n$. By Lemma \[lem280\] the main diagonal of $L$ is an admissible complete main diagonal. Therefore, by definition, the main diagonal of $P$ is completable. Therefore, by Lemma \[lem310\], the main diagonal of $P$ is admissible and hence, by definition, $P$ is admissible.

Both of the symmetric partial latin squares in Figure \[fig260\] are inadmissible. The sensible question to ask now is whether an admissible symmetric partial latin square of order $n$ with $n-1$ prescribed cells is completable. In this case, it was shown by Andersen and Hilton Andersen and Hilton (1994) that the answer is yes. Once again, this is the best possible bound as there are, as shown in Figure \[fig330\], incompletable admissible symmetric partial latin squares of order $n$ with $n$ prescribed cells.

$	$
\left[	\left[
\begin{array}{cccc}	\begin{array}{ccccc}
- & 1 & - & - \	- & 1 & - & - & - \
1 & - & - & - \	1 & - & - & - & - \
- & - & 1 & - \	- & - & 2 & - & - \
- & - & - & 2	- & - & - & 3 & - \
\end{array}	- & - & - & - & 4
]	\end{array}
$	]
$

Once again Andersen and Hilton delved further. This time they came up with a characterisation of completable symmetric partial latin squares with as many as $n+1$ prescribed cells. In Andersen and Hilton (1994) they showed that, essentially, an admissible symmetric partial latin square with upto $n+1$ prescribed cells is completable if and only if it is not one of the eight types defined in Definitions \[def340\]-\[def370\] and illustrated in Figure \[fig400\] or obtainable from one if the incompletable types with $n$ prescribed cells by prescribing a further cell.

\[def340\] A symmetric partial latin square of even order $n$ on $[n]$ with $n$ prescribed cells is Type

if and only if $d(A,1)$ is odd and there exists an even $k<n$ such that $A(1,k)=A(2,k-1)=\ldots =A(k,1)=1$.

\[def350\] A symmetric partial latin square of odd order $n$ on $[n]$ with $n$ prescribed cells is Type

if and only if $d(A,1)=0$ and there exists an even $k\leq n$ such that $A(1,k)=A(2,k-1)=\ldots =A(k,1)=1$ and Type
if and only if $A(n,n)=1$, $A(1,n-1)=A(n-1,1)=2$ and $A(2,n-2),A(3,n-3)=\ldots =A(n-2,2)=1$.

\[def360\] A symmetric partial latin square of even order $n$ on $[n]$ with $n+1$ prescribed cells is Type

if and only if $A(1,1)=3$ and there exists an even $k\leq n$ such that $A(1,k)=A(k,1)=1$, $A(2,k-1)=A(3,k-2)=\ldots =A(k-1,2)=1$ and $A(k+1,k+1)=A(k+2,k+2)=\ldots =A(n,n)=1$ and Type
if and only if $A(1,1)=3$ and there exists an even $k\leq n$ such that $A(1,k)=A(k,1)=2$, $A(k,k)\neq 1$ and $A(k+1,k+1)=A(k+2,k+2)=\ldots = A(n-1,n-1)=1$.

\[def370\] A symmetric partial latin square of odd order $n$ on $[n]$ with $n+1$ prescribed cells is Type

if and only if $A(1,1)=3$, $A(1,n-1)=A(n-1,n-1)=2$ and $A(2,n-2)=A(3,n-3)=\ldots A(n,2)=1$, Type
if and only if $n=5$, $A(1,2)=A(2,1)=1$, $A(1,3)=A(3,1)=2$, $A(4,4)=3$ and $A(5,5)=4$ and Type
if and only if $n=5$, $A(1,2)=A(2,1)=A(3,3)=1$ and $A(1,3)=A(2,2)=A(3,1)=2$.

\[def380\] A bad admissible symmetric partial latin square of order is an admissible symmetric partial latin square $A$, of order $n$, which either has $n$ prescribed cells and is isotopic to a symmetric partial latin square of Type E1, O1 or O2 or has $n+1$ prescribed cells and is either isotopic to a symmetric partial latin square of Type E2, E3, O3, 5A or 5B or has a diagonal cell $(i,i)$ such that $A^{\star(i,i)}$ is isotopic to a symmetric partial latin square of Type E1, O1 or O2. Otherwise a partial latin square of order $n$ with at most $n+1$ prescribed cells is good.

In Andersen and Hilton (1994) Andersen and Hilton proved that the bad admissible symmetric partial latin squares are precisely the incompletable admissible symmetric partial latin squares.

\[Andersen and Hilton @AH3\] \[thm390\] A symmetric partial latin square $P$ of order $n$ with at most $n+1$ prescribed cells is completable if and only if $P$ is admissible and good.

The content of this section has not been directly related to the results of this thesis. The motivation for including this material is to introduce the concepts, language and notation of latin squares and to give an impression of some of the difficulties of the general problem of completing partial latin squares. In Section \[sec410\] results which are of more direct relevance are discussed.

References

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

Andersen, L. D., and A. J. W. Hilton. 1983. “Thank Evans!” Proc. London Math. Soc. 3 (47): 507–22.

Andersen, L. 1985. “Completing Partial Latin Squares.” Mat-Fys. Medd. Danske Vid. Selsk. 41 (1): 23–69.

Damerell, R. M. 1983. “On Smetaniuk’s Construction for Latin Squares and the Andersen-Hilton Theorem.” Proc. London Math. Soc. 3 (47): 523–26.

Andersen, L. 1994. “Symmetric Latin Squares and Complete Graph Analogues of the Evans Conjecture.” J. Combinatorial Designs 2: 197–252.

A diagonal of a latin square in which each symbol occurs exactly once is called a transversal. It follows that every symmetric latin square of odd order has a transversal. A famous open conjecture, due to Ryser, is that every latin square of odd order has a transversal.↩