turkmath.org

Let $N$ represent a set of $n$ distinct elements. A non-empty subset $P$ of $N\times N\times N$ is said to be a {\em partial latin square}, of order $n$, if for all $(x_1,x_2,x_3),(y_1,y_2,y_3)\in P$ and for all distinct $i,j,k\in \{1,2,3\}$, \begin{align*} x_i=y_i\mbox{ and }x_j=y_j\mbox{ implies }x_k=y_k. \end{align*} If $|P|=n^2$, then we say that $P$ is a {\em latin square}, of order $n$. Two partial latin squares $P$ and $Q$, of the same order are said to be {\em orthogonal} if they have the same non-empty cells and for all $r_1,c_1,r_2,c_2,x,y\in N$ \begin{align*} \{(r_1,c_1,x),(r_2,c_2,x)\}\subseteq P\mbox{ implies }\{(r_1,c_1,y),(r_2,c_2,y)\}\not\subseteq Q. \end{align*} In 1960 Evans proved that a partial latin square of order $n$ can always be embedded in some latin square of order $t$ for every $t\geq 2n$. In the same paper Evans raised the question as to whether a pair of finite partial latin squares which are orthogonal can be embedded in a pair of finite orthogonal latin squares. We show that a pair of orthogonal partial latin squares of order $t$ can be embedded in a pair of orthogonal latin squares of order at most $16t^4$ and all orders greater than or equal to $48t^4$. This is the first polynomial embedding result of its kind.