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 partial latin square, of order $n$, if for all $(x_1, x_2, x_3),(y_1, y_2, y_3) ∈ P$ and for all distinct $i, j, k ∈ \{1, 2, 3\}$, \[x_i = y_i \textrm{ and } x_j = y_j \textrm{ implies } x_k = y_k.\] If $|P| = n^2$, then we say that $P$ is a latin square, of order $n$. Two partial latin squares $P$ and $Q$, of the same order are said to be orthogonal if they have the same non-empty cells and for all $r_1, c_1, r_2, c_2, x, y ∈ N$ \[{(r_1, c_1, x),(r_2, c_2, x)} ⊆ P \textrm{ implies } {(r_1, c_1, y),(r_2, c_2, y)} \not\subseteq Q.\] 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.