% EJC papers *must* begin with the following two lines. \documentclass[12pt]{article} \usepackage{e-jc} % Please remove all other commands that change parameters such as % margins or pagesizes. % only use standard LaTeX packages % only include packages that you actually need % we recommend these ams packages \usepackage{amsthm,amsmath,amssymb} % we recommend the graphicx package for importing figures \usepackage{graphicx} \usepackage{pstricks} \newrgbcolor{nearlywhite}{0.92 0.92 0.92} % use this command to create hyperlinks (optional and recommended) \usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref} % use these commands for typesetting doi and arXiv references in the bibliography \newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}} \newcommand{\arxiv}[1]{\href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}} % all overfull boxes must be fixed; % i.e. there must be no text protruding into the margins % declare theorem-like environments \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{fact}[theorem]{Fact} \newtheorem{observation}[theorem]{Observation} \newtheorem{claim}[theorem]{Claim} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{open}[theorem]{Open Problem} \newtheorem{problem}[theorem]{Problem} \newtheorem{question}[theorem]{Question} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % if needed include a line break (\\) at an appropriate place in the title \title{\bf Maximal partial Latin cubes} % input author, affiliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Thomas Britz\\ \small School of Mathematics and Statistics\\[-0.8ex] \small UNSW Australia, NSW 2052, Australia\\[-0.8ex] \small\tt britz@unsw.edu.au\\ \and Nicholas J.~Cavenagh\\ \small Department of Mathematics\\[-0.8ex] \small The University of Waikato\\[-0.8ex] \small Private Bag 3105, Hamilton 3240, New Zealand\\[-0.8ex] \small\tt nicholas\_cavenagh@yahoo.co.uk\\ \and Henrik Kragh S{\o}rensen\\ \small Centre for Science Studies\\[-0.8ex] \small Department of Mathematics\\[-0.8ex] \small Aarhus University\\[-0.8ex] \small Ny Munkegade 120, Building 1520, DK-8000 Aarhus C, Denmark\\[-0.8ex] \small\tt hks@css.au.dk } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Oct 3, 2014}{?}\\ \small Mathematics Subject Classifications: 05B15} \begin{document} \maketitle \begin{abstract} We prove that each maximal partial Latin cube must have more than $29.289\%$ of its cells filled and show by construction that this is a nearly tight bound. We also prove upper and lower bounds on the number of cells containing a fixed symbol in maximal partial Latin cubes and hypercubes, and we use these bounds to determine for small orders $n$ the numbers~$k$ for which there exists a maximal partial Latin cube of order $n$ with exactly $k$ entries. Finally, we prove that maximal partial Latin cubes of order $n$ exist of each size from approximately half-full ($n^3/2$ for even $n\geq 10$ and $(n^3+n)/2$ for odd $n\geq 21$) to completely full, except for when either precisely $1$ or $2$ cells are empty. % keywords are optional \bigskip\noindent \textbf{Keywords:} Maximal partial Latin cube, bound, construction, transversal \end{abstract} \newpage \section{Introduction} \label{sec:intro} %In this paper we pose the question: %How many filled cells can a partial Latin cube have so that no more cells can be completed? The famous theorem known as the Evans Conjecture, posed by Evans~\cite{evans60} and proved independently by Anderson and Hilton~\cite{AnHi83}, H{\"a}ggkvist~\cite{haggkvist78}, and Smetaniuk~\cite{smetaniuk81}, states that it is possible to complete each partial Latin square of order $n$ with at most $n-1$ elements. In contrast, simple examples such as \[ \begin{array}{|c|c|}\hline 1&\\\hline&2\\\hline\end{array} \] show that it is not always possible to complete such squares if they contain $n$ or more elements. A partial Latin square like the one above is {\em maximal} if none of its empty cells can be filled. A natural question arises: how many elements may there be in a maximal partial Latin square? This question was answered almost completely in~\cite{HoRa}. In the present paper, we investigate an analoguous question, namely that of determining the possible numbers of elements in maximal partial Latin {\em cubes}. We prove that each maximal partial Latin cube of order $n$ must have more than $(1-1/\sqrt{2})n^3 > 0.29289n^3$ of its $n^3$ cells filled (cf.~Theorem~\ref{thm:mainbound}) and we show by construction that this is close to being a tight bound (cf.~Theorem~\ref{thm:existence}). We further prove upper and lower bounds on the number of entries of a fixed symbol, or in a fixed layer, in maximal partial Latin cubes, and we generalise these bounds with respect to maximal partial Latin {\em hypercubes} (cf.~Theorem~\ref{thm:manyboundshyper}). Using these bounds, we determine for orders 2, 3 (and almost for order~4), which numbers~$k$ there exists a maximal partial Latin cube with exactly $k$ entries (cf.~Theorem~\ref{thm:computation}). We also prove that maximal partial Latin cubes of order $n$ with each size from approximately half-full ($n^3/2$ for even $n$ and $(n^3+n)/2$ for odd $n$) to completely full exist (for $n\geq 21$), except for when either precisely $1$ or $2$ cells are empty (cf.~Theorems~\ref{thm:evencase} and~\ref{thm:oddcase}). \section{Preliminaries} \label{sec:preliminaries} Let $[n] = \{1,2,\dots,n\}$. A {\em partial Latin square} of {\em order} $n$ is a set $L$ of ordered triples from $[n]^3$ such that if $(r,c,s)$ and $(r',c',s')$ are distinct elements of $L$, at most one of the following is true: $r=r'$; $c=c'$; $s'=s$. We typically represent a Latin square as an $n\times n$ array, with {\em symbol} $s$ in {\em row} $r$ and {\em column} $c$ if and only if $(r,c,s)\in L$. Each symbol then occurs at most once per row and at most once per column. A partial Latin square with $n^2$ elements is a {\em Latin square}. We may extend Latin squares by an extra dimension in the following manner. A {\em partial Latin cube} $L$ of order $n$ is a subset of %$4$-tuples from $[n]^4$ such that if $(\ell,r,c,s)$ and $(\ell',r',c',s')$ are distinct elements of $L$, then at most two of the following are true: $\ell=\ell'$; $r=r'$; $c=c'$; $s=s'$. Here, $\ell$ is the {\em layer}; $r$ is the {\em row}; $c$ is the {\em column}; and $s$ is the {\em symbol}. We typically represent a partial Latin cube as a set of partial Latin squares (layers) such that no symbol occurs in the same row and column of two distinct layers. Thus the set $L_{\ell}:=\{(r,c,s)\mid (\ell,r,c,s)\in L\}$ is a partial Latin square for each $\ell\in [n]$; these partial Latin squares form the layers of $L$. If $(\ell,r,c,s)\in L$, then we may say that symbol $s$ is in {\em cell} $(\ell,r,c)$ of $L$ {\em or} that symbol $s$ is in {\em cell} $(r,c)$ of layer $\ell$ of $L$. In either case, we say that this cell is {\em filled}; conversely, if $(\ell,r,c,s)\notin L$ for all symbols~$s$, then the cell $(\ell,r,c)$ is {\em empty}. The {\em lines} of a partial Latin cube are obtained by fixing any two of the first three coordinates and allowing the remaining coordinate to vary. The lines obtained by fixing the second and third coordinates will be known as {\em stacks}. If the layers of the partial Latin cube are stacked directly on top of each other, then the stacks are the vertical columns formed. Thus, a partial Latin cube can be seen as a 3-dimensional array with symbols occurring at most once in each line. A partial Latin cube of order $n$ with size $n^3$ is a {\em Latin cube}. A partial Latin square (cube) $L$ of order $n$ is said to be {\em maximal} if $L=L'$ whenever $L'$ is a partial Latin square (cube) of the same order $n$ and $L\subseteq L'$. In other words, $L$ is maximal if it is impossible to add any new elements to $L$. Here is a maximal partial Latin cube of order 2, represented by its two layers: \[ \begin{array}{|c|c|}\hline 1& \\\hline &2\\\hline\end{array}\qquad \begin{array}{|c|c|}\hline &2\\\hline1& \\\hline\end{array} \] In \cite{HoRa}, the spectrum of sizes of maximal partial Latin squares is studied and determined with only a small range of possible exceptions. In this paper, we investigate the spectrum of sizes of maximal partial Latin cubes. However, we begin by summarizing results on maximal partial Latin squares, some of which we will use in later sections. First, we emphasize the values which are not in the spectrum. Let $ML(n)$ be the set of integers $t$ for which there exists a maximal partial Latin square of order $n$ with size $t$ (i.e. exactly $t$ filled cells). \begin{theorem} {\rm \cite{HoRa}} \label{HoRa} Let $t$ be an integer such that either: \begin{enumerate} \item $t<\frac{1}{2}n^2$; or \item $t=\frac{1}{2}n^2+k$, $1\leq k\leq \frac{1}{2}n$ where $k$ is odd and $n$ is even; or \item $t=\lceil \frac{1}{2}n^2\rceil +k$, $1\leq k< \frac{1}{2}(n-1)$ where $k$ is odd and $n$ is odd; or \item $t=n^2-1$. \end{enumerate} Then $t\not\in ML(n)$. \label{notinspec} \end{theorem} Next we describe values which are known to be in the spectrum: \begin{theorem} {\rm \cite{HoRa}} Let $t$ be an integer such that $\frac{1}{2}n^2\leq t< n^2-1$ and $t\neq \lceil \frac{1}{2}n^2\rceil +k$, where $k$ is odd and $1\leq k\leq n-1$. Then $t\in ML(n)$. \end{theorem} This leaves the following open problem. \newpage\noindent {\bf Open problem} \cite{HoRa}\; Determine whether $t\in ML(n)$, where: \begin{enumerate} \item $t=\frac{1}{2}n^2+k$, $n$ even, $k$ odd, $\frac{1}{2}n< k\leq n-1$; \item $t=\frac{1}{2}(n^2+1)+k$, $n$ odd, $k$ odd, $\frac{1}{2}(n-1)\leq k\leq n-1$. \end{enumerate} %MAKE THE ABOVE A CONJECTURE? It is conjectured in \cite{HoRa} that the above values of $t$ do {\em not} belong to the spectrum of possible sizes of maximal partial Latin squares. In this paper, we examine the analogous question for partial Latin cubes and define $ML(3,n)$ to be the set of integers $t$ such that there exists a maximal partial Latin cube of order $n$ with exactly $t$ filled cells. It turns out that, in contrast to maximal partial Latin squares, there exist maximal partial Latin cubes with much less than half of the cells filled (cf.~Theorem~\ref{thm:existence}). Conversely, $ML(3,n)$ contains all values between $n^3/2$ and $n-3$ when $n$ is even and $n\geq 10$ and all values between $(n^3+n)/2$ and $n-3$ when $n$ is even and $n\geq 21$ (cf.~Theorems~\ref{thm:evencase} and~\ref{thm:oddcase}). Related to the problem of constructing maximal partial Latin cubes is the question of whether a partial Latin cube is completable. We briefly summarize the literature in this area. A {\em Latin cuboid} is a partial Latin cube with each layer either completely full or empty. Clearly a Latin cuboid cannot be maximal unless it is a Latin cube. In the 1980s, several authors \cite{Fu, Horak, Kochol} considered the problem of constructing non-completable $n\times n\times (n-2)$ Latin cuboids. Subsequently, Kochol~\cite{Koc95} proved that for any $k$ and $n$ satisfying $\frac{1}{2} n < k \le n-2$, there is a non-completable $n\times n\times k$ Latin cuboid. In \cite{BCMP}, constructions for non-completable $n\times n\times k$ Latin cuboids are given in which $k = \lfloor n/2\rfloor$, for any $n$ not congruent to $1$ mod $4$ and greater than~$6$. Little is known about the embedding of a partial Latin cube into a complete Latin cube of higher order. Cruse~\cite{Cr} showed that any $n\times n\times r$ Latin cuboid with $r\leq n$ can be embedded in a Latin cube of order~$n^3$. Denley and \"Ohman~\cite{DeOh2014} prove sufficient conditions for when a $m\times\ell\times k$ {\em Latin box}, i.e., a partial Latin cube whose filled cells form a $m\times \ell\times k$ rectangular box, can be extended to a $n\times \ell\times k$ Latin box and when it can be extended to a $n\times n\times k$ Latin cuboid. They also proved a cube analogue of Evan's Conjecture by proving that any partial Latin cube of order $n$ with at most $n-1$ filled cells is completable under certain conditions on the relative positions of the filled cells. %Cutler and \"Ohman \cite{CO06} showed for all $m$ that every %$2mk\times 2mk\times m$ latin cuboid is extendible, provided $k$ is %sufficiently large. Little else is known about extendibility aside %from the elementary observations that all $n\times n\times 1$ and %$n\times n\times(n-1)$ latin cuboids are extendible (in fact %completable). Of course, by extending any non-completable latin cuboid %as far as possible we will obtain at least one non-extendible latin %cuboid, but often only one of dimensions $n\times n\times(n-2)$. \section{Lower bounds} \label{sec:lowerbounds} We begin with an elementary bound. \begin{proposition} \label{prop:firstbound} If $t\in ML(3,n)$, then $t\geq n^4/(4n-3)$. \end{proposition} \begin{proof} If $L$ is a maximal partial Latin cube with $t$ elements, then $[n]^4$ is the union of the $t$ following unions of lines associated to each $(\ell,r,c,s)\in L$: \[ \{(\ell',r, c ,s ) \!\mid\! \ell'\!\in\![n]\}\cup \{(\ell ,r',c ,s ) \!\mid\! r'\!\in\![n]\}\cup \{(\ell ,r ,c',s ) \!\mid\! c'\!\in\![n]\}\cup \{(\ell ,r ,c ,s') \!\mid\! s'\!\in\![n]\}. \] Each of these line unions contains $4n-3$ elements, so $t(4n-3)\geq n^4$.\qquad \end{proof} The above bound is achieved exactly when $n=3$. In larger orders where, for example, symbols may appear twice within a layer, the bound cannot be achieved. The following theorem offers an improvement for sufficiently large values of~$n$. \begin{theorem} \label{thm:mainbound} If $t\in ML(3,n)$, then $t > (1-1/\sqrt{2})n^3 > 0.29289n^3$. \end{theorem} \begin{proof} Let $L$ be a maximal partial Latin cube with $t$ filled cells. Let $m$ be the least number of filled cells in a layer; then $t\geq nm$. Let $\ell$ be a fixed layer of $L$ with exactly $m$ filled cells and note that $m\geq n$ since each layer must trivially contain at least $n$ filled cells. Let $r_i$ (resp., $c_i$) be the number of filled cells in row $i$ (resp., column $i$) of layer~$\ell$. Observe that $\sum_{i=1}^{n}r_i = \sum_{i=1}^{n}c_i = m$. For each $i\in [n]$, let ${\mathcal C}_i$ be the set of columns $c$ such that cell $(\ell,i,c)$ is empty. Then $|{\mathcal C}_i| = n-r_i$. For each $i$, define $\alpha_i$ to be the number of filled cells in the columns $[n]\setminus {\mathcal C}_i$ of layer $\ell$. For each $c\in {\mathcal C}_i$, the maximality of $L$ implies that there must be at least $n-r_i$ filled cells in the union of column $c$ of layer $\ell$ and the stack with row $i$ and column $c$. Thus, there are at least $(n-r_i)^2$ filled cells which occur in some column $c\in {\mathcal C}_i$ either within layer $\ell$ {\em or} within row $i$ in some layer $\ell'\neq \ell$. Since $\ell$ has $m$ filled cells, exactly $m-\alpha_i$ filled cells are in the former category, so at least $(n-r_i)^2-(m-\alpha_i)$ are in the latter category. Thus there are at least \[ \sum_{i=1}^{n} [(n-r_i)^2-(m-\alpha_i)] = \sum_{i=1}^{n} [n^2 - 2nr_i + r_i^2 - m + \alpha_i] = n^3 - 3nm + \sum_{i=1}^{n} r_i^2 + \sum_{i=1}^{n}\alpha_i \] filled cells not in layer $\ell$, so \[ t\geq n^3-3nm+\sum_{i=1}^{n} r_i^2+\sum_{i=1}^{n}\alpha_i + m\,. \] Now consider the term $\sum_{i=1}^{n}\alpha_i$ in the above expression. Within layer $\ell$ a fixed column $j$ intersects a row $i$ for exactly $c_j$ choices of~$i$. Each time such an intersection occurs, there is a contribution of $c_j$ towards the sum $\sum_{i=1}^{n}\alpha_i$ due to filled cells within column~$j$. Thus each column $j$ contributes $c_j^2$ to the sum $\sum_{i=1}^{n}\alpha_i$, so \[ t\geq n^3-3nm+\sum_{i=1}^{n} r_i^2+\sum_{j=1}^{n} c_j^2+m\,. \] Since $\sum_{i=1}^{n} r_i=\sum_{j=1}^{n} c_j = m$, by the Cauchy-Schwarz inequality, \begin{equation} t \geq n^3-3nm+2m^2/n+m\,. \label{firstonewithm} \end{equation} In particular, % (observing that $m$ is a relatively insignificant term in the above expression), \begin{equation} t > n^3-3nm+2m^2/n\,. \label{firstone} \end{equation} Suppose, for the sake of contradiction, that $tn^3(1-1/\sqrt{2})+n^2(\sqrt{2}-1)/4+n/(16\sqrt{2})+1/(32\sqrt{2})$ %IS IT WORTH IT THOUGH? Note that it is possible to sharpen the bound in Theorem~\ref{thm:mainbound} just slightly, by applying a Taylor series to the inequality (\ref{firstonewithm}) instead of (\ref{firstone}) as in the proof: \[ t > n^3(1-1/\sqrt{2})+n^2(\sqrt{2}-1)/4+n/(16\sqrt{2})+1/(32\sqrt{2})\,. \] This does not however provide any asymptotic improvement. \section{Bounds on the number of cells of a given symbol} \label{sec:specificbounds} We can also find a lower bound on the number of cells filled with a given symbol. Consider a maximal partial Latin cube $L$ of order $n$ and let $\chi_1,\ldots,\chi_n$ denote the number of cells in $L$ filled with symbols $1,\ldots,n$, respectively, and assume without loss of generality that $\chi_1\geq\cdots\geq \chi_n$. \begin{proposition} \label{prop:lowerboundsplus} If $t\in ML(3,n)$ and $\displaystyle j := \Bigl\lceil\frac{n^3-t}{3(n-1)}\Bigr\rceil$, %$\displaystyle j := \max_{\mu\in\mathbb{R}\;:\; 3<\mu<3n} % \Bigl\lceil\frac{n^3 - t + (3-\mu)n}{3n-\mu}\Bigr\rceil$, then for each $i\in[n]$, \[ \max\{j,n\}\leq \chi_i \leq n^2\,. \] \end{proposition} \begin{proof} Let $i\in[n]$ and consider a maximal partial Latin cube $L$ of order~$n$. No symbol can appear more than $n$ times in any given cube layer, so $\chi_i\leq n^2$. Also, $\chi_i\geq n$, since if this were not true, then there would be some row and some column that did not contain symbol~$i$; but then their intersecting stack would contain at least one empty cell that could be filled with this symbol, thus contradicting the maximality of $L$. Finally, each of the $n^3$ cells is either filled with one of the symbols $1,\ldots,i-1,i+1,\ldots,n$ or is in the same line as some cell that is filled by symbol~$i$. %(This observation is true regardless of the symbol chosen.) Since each cell shares lines with $3n-2$ cells, \[ (3n-2)\chi_i + \sum_{i'\neq i}\chi_{i'}\geq n^3\,. \] Subtracting $t = \chi_1+\cdots+\chi_n$ gives $3(n-1)\chi_i\geq n^3 - t$. %Then for any real number $\mu$ with $3<\mu<3n$, %\[ % (3n-\mu)\chi_i % = (3n-2)\chi_i + (2-\mu)\chi_i % \geq n^3 - \sum_{i'\neq i}\chi_{i'} + (2-\mu)\chi_i % = n^3 - t + (3-\mu)\chi_i\,. %\] %so $(3n-\mu)\chi_i \geq n^3 - t + (3-\mu)n$\,, %Since $\chi_i\geq n$, % Use a sharper bound here? %it follows that $(3n-\mu)\chi_i \geq n^3 - t + (3-\mu)n$. Hence, $\chi_i \geq j$. %Note that the minimality of $\chi_{n-1}$ was not used here. \qquad\end{proof} Although Proposition~\ref{prop:firstbound} and Theorem~\ref{thm:mainbound} provide better overall lower bounds on the numbers of filled cells than does Proposition~\ref{prop:lowerboundsplus}, the latter provides more precise information on the required number of filled cells of each symbol. Proposition~\ref{prop:lowerboundsplus} can also be used to provide upper bounds on the number of cells filled with a particular symbol. \begin{theorem} \label{thm:upperbounds} If $t\in ML(3,n)$ and $\displaystyle j := \Bigl\lceil\frac{n^3-t}{3(n-1)}\Bigr\rceil$, then for each $i\in[n]$, \[ \chi_i \leq \min\{\lfloor (t - (n-i)\max\{j,n\})/i\rfloor,n^2\}\,. \] In particular, no symbol can appear in more than $t - (n-1)\max\{j,n\}$ cells. \end{theorem} \begin{proof} %By Theorem~\ref{thm:lowerbounds}, By Proposition~\ref{prop:lowerboundsplus}, $\chi_{i'} \geq \max\{j,n\}$ for all $i'\in[n]$, so \[ \chi_1 + \cdots + \chi_i = t - (\chi_{i+1} + \cdots + \chi_n) \leq t - (n-i)\max\{j,n\}\,. \] The first part of the theorem follows from the inequalities $\chi_1\geq\cdots\geq \chi_i$ and from Proposition~\ref{prop:lowerboundsplus}. The second part is obtained by setting $i = 1$. \qquad\end{proof} The lower bounds in Proposition~\ref{prop:lowerboundsplus} may be tightened considerably by applying averaging arguments to the upper bounds in Theorem~\ref{thm:upperbounds}. \begin{theorem} \label{thm:lowerbounds} If $t\in ML(3,n)$ and $\displaystyle j := \Bigl\lceil\frac{n^3-t}{3(n-1)}\Bigr\rceil$, then for each $i\in[n]$, \[ \chi_i \geq \max\Bigl\{\max_{I\subseteq [n]\::\:i = \min I} \Bigl\lceil\Bigl(t-\sum_{i'\in[n]-I}\min\{\lfloor (t - (n-i')\max\{j,n\})/i'\rfloor,n^2\}\Bigr)/|I|\Bigr\rceil,j,n\Bigr\}\,. \] \end{theorem} \begin{proof} For each set $I\subseteq [n]$, \[ \sum_{i''\in I} \chi_{i''} = t - \sum_{i'\in[n]-I} \chi_{i'} \] and if $i = \min I$, then $\chi_i = \max \{\chi_{i''}\,:\,i''\in I\}$, so \[ \chi_i \geq \Bigl\lceil\Bigl(t - \sum_{i'\in[n]-I} \chi_{i'}\Bigr)/|I|\Bigr\rceil\,. \] Applying Theorem~\ref{thm:upperbounds} to $\chi_{i'}$, and Proposition~\ref{prop:lowerboundsplus}, concludes the proof. \qquad\end{proof} \begin{example}{\rm \label{exa:lowerbounds} In maximal partial Latin cubes of order $n = 4$, the least number of cells that each of the $n$~symbols must fill is given by Proposition~\ref{prop:lowerboundsplus}, illustrated as the lower black line in the grid below, where $t$ is the number of filled cells. Theorem~\ref{thm:lowerbounds} generally gives far better individual lower bounds on $\chi_1,\ldots,\chi_4$. Meanwhile, Theorem~\ref{thm:upperbounds} offers good individual uppers bounds thereon. These individual upper and lower bounds are given by pairs of lines drawn in black ($\chi_1$), dashed ($\chi_2$), dotted ($\chi_3$), and dash-dotted~($\chi_4$). \begin{center} \psset{unit=2.6mm,linearc=0,fillcolor=white,gridcolor=nearlywhite,gridlabelcolor=white,subgriddiv=1} \begin{pspicture}(17,-3)(67,19) \psgrid(19,0)(64,16) \psframe*[linecolor=white](47, 1)(63, 3)\psframe[linecolor=nearlywhite,linewidth=.4pt](47, 1)(63, 3) \psframe*[linecolor=white](25,13)(27,15)\psframe[linecolor=nearlywhite,linewidth=.4pt](25,13)(27,15) \psframe*[linecolor=white](33,13)(35,15)\psframe[linecolor=nearlywhite,linewidth=.4pt](33,13)(35,15) \psframe*[linecolor=white](42,13)(44,15)\psframe[linecolor=nearlywhite,linewidth=.4pt](42,13)(44,15) \psframe*[linecolor=white](50,13)(52,15)\psframe[linecolor=nearlywhite,linewidth=.4pt](50,13)(52,15) \rput(55,2){\small universal lower bound} \psline(19,4)(20,5)(21,6)(24,6)(25,7)(28,7)(29,8)(32,8)(33,9)(36,9)(37,10)(40,10)(41,11)(44,11)(45,12)(48,12)(49,13)(52,13)(53,14)(56,14)(57,15)(60,15)(61,16)(64,16) \psline(20,5)(27,12)(28,16)(64,16) \psline[linestyle=dashed](20,5)(21,5)(27,5)(28,4)(29,5)(31,5)(32,6)(34,6)(35,7)(37,7)(38,8)(40,8)(41,9)(43,9)(44,10)(46,10)(47,11)(49,11)(50,12)(52,12)(53,13)(55,13)(56,14)(58,14)(59,15)(61,15)(62,16)(64,16) \psline[linestyle=dashed](20,5)(21,5)(22,6)(23,6)(24,7)(25,7)(26,8)(27,8)(28,10)(29,10)(30,11)(31,11)(32,12)(33,12)(34,13)(35,13)(36,14)(37,14)(38,15)(39,15)(40,16)(64,16) \psline[linestyle=dashed,dash=1pt 3pt 1pt 3pt](20,5)(27,5)(28,4)(40,4)(41,5)(42,5)(43,6)(44,6)(45,7)(46,7)(47,8)(48,8)(49,9)(50,9)(51,10)(52,10)(53,11)(54,11)(55,12)(56,12)(57,13)(58,13)(59,14)(60,14)(61,15)(62,15)(63,16)(64,16) \psline[linestyle=dashed,dash=1pt 3pt 1pt 3pt](20,5)(22,5)(23,6)(25,6)(26,7)(27,7)(28,8)(30,8)(31,9)(33,9)(34,10)(36,10)(37,11)(38,11)(39,12)(41,12)(42,13)(44,13)(45,14)(47,14)(48,15)(50,15)(51,16)(64,16) \psline[linestyle=dashed,dash=4pt 2pt 1pt 2pt](20,5)(27,5)(28,4)(52,4)(64,16) \psline[linestyle=dashed,dash=4pt 2pt 1pt 2pt](20,5)(23,5)(24,6)(27,6)(28,7)(31,7)(32,8)(35,8)(36,9)(39,9)(40,10)(43,10)(44,11)(47,11)(48,12)(51,12)(52,13)(55,13)(56,14)(59,14)(60,15)(63,15)(64,16) \psline(19,5)(27,5)(28,4)(64,4) \psline{->}(19,0)(66,0) \psline{->}(19,0)(19,18) \psline(19, 0)(18.5, 0) \psline(19, 2)(18.5, 2) \psline(19, 5)(18.5, 5) \psline(19,16)(18.5,16) \psline(19, 0)(19,-.5) \psline(28, 0)(28,-.5) \psline(40, 0)(40,-.5) \psline(52, 0)(52,-.5) \psline(64, 0)(64,-.5) \rput(19,-2){19} \rput(28,-2){28} \rput(40,-2){40} \rput(52,-2){52} \rput(64,-2){64} \rput(17, 0){ 0} \rput(17, 2){ 2} \rput(17, 5){ 5} \rput(17,16){16} \rput(67, 0){$t$} \rput(26, 14){$\chi_1$} \rput(34, 14){$\chi_2$} \rput(43, 14){$\chi_3$} \rput(51, 14){$\chi_4$} \end{pspicture} \end{center} It is immediately visible from the bounds above that $19\notin ML(3,4)$ since the lower bound is higher than one of the upper bounds at $t = 19$. Similarly, the bounds for $t = 20$ dictate that $\chi_1 = \cdots = \chi_4 = 5$, and a simple counting argument shows that this is not possible; this shows that $20\notin ML(3,4)$.} \end{example} Example~\ref{exa:lowerbounds} also illustrates the following open problem. \smallskip \noindent{\bf Open Problem}. Are the true minimal values for $\chi_i$ non-decreasing for fixed~$i$ and increasing values of~$t\in ML(3,n)$? \medskip It does not appear to be possible to improve the upper or lower bounds on $\chi_i$ further by the methods that we have used above. However, let $\lambda_i$, $\rho_i$, and $\gamma_i$ denote the number of filled cells in layer~$i$, row~$i$, and column~$i$, respectively, and assume without loss of generality that $\lambda_1\geq\cdots\geq\lambda_n$, $\rho_1 \geq\cdots\geq\rho_n$, and $\gamma_1 \geq\cdots\geq\gamma_n$. Since the maximality of a partial Latin square is invariant under permutations of the layer, row, column, and symbol coordinates of the 4-tuples $(x,y,z,c)\in[n]^4$, we can significantly generalise the bounds from Theorems~\ref{thm:upperbounds} and~\ref{thm:lowerbounds}. \begin{theorem} \label{thm:manybounds} If $t\in ML(3,n)$ and $\displaystyle j := \Bigl\lceil\frac{n^3-t}{3(n-1)}\Bigr\rceil$, then for each $i\in[n]$, \[ f(i) \geq \lambda_i,\rho_i,\gamma_i,\chi_i \geq \max\Bigl\{j,n,\max_{I\subseteq [n]\::\:i = \min I} \Bigl\lceil\Bigl(t-\sum_{i'\in[n]-I} f(i')\Bigr)/|I|\Bigr\rceil\Bigr\} \] where $f(i) := \min\{\lfloor (t - (n-i)\max\{j,n\})/i\rfloor,n^2\}$. \end{theorem} We may generalise these results and their proofs further. Define a partial Latin {\em hypercube} $L$ of dimension~$d$ and order $n$ to be a set of $(d+1)$-tuples from $[n]^{d+1}$ such that if $(v_1,\ldots,v_{d+1})$ and $(v'_1,\ldots,v'_{d+1})$ are distinct elements of~$L$, then $v_i = v'_i$ for at most $d-1$ values of~$i$. Let $ML(d,n)$ denote the set of numbers~$t$ for which some {\em maximal} partial Latin hypercube of dimension~$d$ and order $n$ contains exactly~$t$ elements. Let $L$ be such a maximal partial Latin hypercube and let $\chi^\ell_i$ denote the number of elements of $L$ whose $\ell$th coordinate has value~$i$. Also, assume that $\chi^\ell_1\geq\cdots\geq\chi^\ell_n$. The following result is a hypercube generalisation of (most of) Theorem~\ref{thm:manybounds}. \begin{theorem} \label{thm:manyboundshyper} If $t\in ML(d,n)$ for $d\geq 2$ and $\displaystyle j := \Bigl\lceil\frac{n^d-t}{d(n-1)}\Bigr\rceil$, %and $\displaystyle k := \Bigl\lceil \frac{n^{d-1}}{d(n-1)+1}\Bigr\rceil$, then for each $\ell\in[d+1]$ and each $i\in[n]$, \[ f(i) \geq \chi^\ell_i \geq \max\Bigl\{j,\max_{I\subseteq [n]\::\:i = \min I} \Bigl\lceil\Bigl(t-\sum_{i'\in[n]-I} f(i')\Bigr)/|I|\Bigr\rceil\Bigr\} \] where $f(i) := \lfloor (t - (n-i)j)/i\rfloor$. \end{theorem} \section{Spectra for small values of \texorpdfstring{$n$}{n}} \label{sec:computation} \noindent By inspection and by extensive computer search, we found the following (partial) spectra for the number of filled entries in maximal partial Latin cubes of orders $n=2,3,4$, respectively. \begin{theorem} \label{thm:computation} \[ \begin{array}{rl} ML(3,2) &= \{4,5,8\}\\ ML(3,3) &= \{9,12,14,\ldots,24,27\}\\ ML(3,4) &= \{31,\ldots,61,64\}\cup S\quad\textit{where}\quad S\subseteq\{28,29,30\}\,. \end{array} \] \end{theorem}% The Appendix presents examples of maximal partial Latin cubes for each of the spectrum values given in Theorem~\ref{thm:computation} above. The parallelised computer search used the results of Section~\ref{sec:specificbounds}, most particularly Theorem~\ref{thm:manybounds} and Example~\ref{exa:lowerbounds}, to harshly prune the search tree. The cube of order~4 lent itself nicely to fast 64 bit representation, and precalculated permutation groups and subgroups were used together with shortcuts and optimisations to further prune the search tree and speed up the search. We leave it as a challenging computational problem to determine whether each of the values 28, 29 and 30 is a member of $ML(3,4)$. \newpage \section{Constructions with less than half of cells filled} \label{sec:lessthanhalf} In this section we show the existence of maximal partial Latin cubes with a small number of filled cells for any order $n$. Small in this case will be $n^3/3+O(n^2)$. First consider the case in which $n$ is divisible by $3$ and write $n=3N$. There exists a maximal partial Latin cube $L$ of order~$3$ with $9$ filled cells (see Theorem~\ref{thm:computation}). Replace each filled cell of $L$ containing symbols $i\in \{1,2,3\}$ by a Latin cube of order $N$ on element set $\{iN+1,iN+2,\ldots,(i+1)N\}$. The resultant Latin cube $L_{3N}$ is clearly a maximal partial Latin cube of order~$n=3N$ with $n^3/3 = 9N^3$ filled cells. Now suppose that $n$ is not divisible by~$3$. For the sake of brevity, we use an existence proof to give an upper bound, rather than a completely explicit construction. The idea is based on the following simple observation. \begin{lemma} Every partial Latin cube of order $n$ is contained in a maximal partial Latin cube of order~$n$. \end{lemma} Suppose that $n=3N+1$ where $N\geq 1$. Take the partial Latin cube $L_{3N}$ from above and add an empty row, an empty column and an empty layer to create a partial Latin cube of order $n=3N+1$. We then greedily add elements to filled cells until the resultant partial Latin cube is maximal. Each symbol occurs at most once per line, so the symbol $3N+1$ can be added to at most $n^2$ empty cells, and each symbol $s\in[3N]$ can be added to fewer than $3n$ empty cells, each appearing in the final row, column and layer. The resultant maximal partial Latin cube thus has fewer than $9N^3+n^2+(3n)(3N)$ filled cells, and we therefore obtain the following lemma. \begin{lemma} Let $n-1$ be divisible by $3$ and $n\geq 4$. Then there exists a maximal partial Latin cube of order $n$ with no more than $(n^3+9n^2-6n-4)/3$ filled cells. \end{lemma} The argument for the case in which $n=3N+2$ is similar, adding an extra empty row, column and layer. The resultant maximal partial Latin cube has at most $9N^3 + 18nN + 2n^2$ filled cells. \begin{lemma} Let $n-2$ be divisible by $3$ and $n\geq 5$. Then there exists a maximal partial Latin cube of order~$n$ with at most $(n^3+21n^2-3n-4)/3$ filled cells. \end{lemma} The linear terms above may be improved; for simplicity however, we summarize the results from this section as follows: \begin{theorem} \label{thm:existence} For each order $n\geq 3$ there exists a maximal partial Latin cube of order $n$ with $n^3/3+O(n^2)$ filled cells. \end{theorem} \newpage \section{Spectra for at least half-full partial Latin cubes} \label{sec:atleasthalffull} In this section, we show that maximal partial Latin cubes of any size from approximately half-full to completely full exist (for orders $n\geq 21$) unless either $1$ or $2$ cells are empty. We first show that neither $n^3-1$ nor $n^3-2$ belong to $ML(3,n)$. To this end, we need the following lemma. \begin{lemma} If $L$ is a maximal partial Latin cube with $n^3-t'$ filled cells where $t'>0$, then there are two empty cells $(\ell,r,c)$, $(\ell',r',c')$ for which $r \neq r'$, $c \neq c'$ and $\ell\neq \ell'$. \end{lemma} \begin{proof} For a contradiction and without loss of generality, suppose that all empty cells in $L$ belong to a single layer $\ell$. Then every other layer of $L$ is a Latin square. Suppose that cell $(\ell,r,c)$ is empty. There is precisely one symbol $s$ which does not occur in the stack defined by $(r,c)$. If $(\ell,r',c,s)\in L$ for some $r\neq r'$, then symbol $s$ occurs $n$ times within the Latin square $L'$ defined by fixing $c$ but $0$ times within row $r$ of $L'$, a contradiction. Similarly, $(\ell,r,c',s)\not\in L$ for any $c'\neq c$. Thus, we may place symbol $s$ in cell $(\ell,r,c)$, contradicting the maximality of $L$. \qquad\end{proof} \begin{corollary} \label{cor:notminusone} $n^3-1\not\in ML(3,n)$. \end{corollary} \begin{lemma} \label{lem:notminustwo} $n^3-2\not\in ML(3,n)$. \end{lemma} \begin{proof} Suppose for the sake of contradiction that $L$ is a maximal partial Latin cube of order $n$ with only $2$ empty cells; let these be $(\ell,r,c)$ and $(\ell',r',c')$. By the previous lemma, $\ell\neq \ell'$, $r\neq r'$ and $c\neq c'$. Thus the partial Latin squares defined by fixing $\ell$, $r$ or $c$ each have exactly one empty cell. By Theorem~\ref{notinspec}, there is no maximal partial Latin square of order~$n$ with exactly one missing cell. Thus, the three partial Latin squares that include $(\ell,r,c)$ are each completable to a Latin square. In particular, there is a unique symbol~$s$ which occurs in none of the lines $(\ell,r)$, $(r,c)$ and $(\ell,c)$. Thus $L$ is not maximal, a contradiction. \qquad\end{proof} Next, we focus on the upper half of the spectrum $ML(3,n)$. %the rest of the spectrum for maximal partial Latin cubes with %at least half of their cells filled. %%We make use of some constructions of maximal partial Latin squares in \cite{HoRa}. We will make use of the following construction for a partial Latin cube from two partial Latin squares; see, for example~\cite[Section~5]{LHC}. \begin{lemma} Let $L_1$ and $L_2$ be two partial Latin squares of order~$n$. Then \vspace*{-2mm} \[ L_1\circ L_2 := \{(\ell,r,c,s)\mid (r,c,x)\in L_1\,, (\ell,s,x)\in L_2 \mbox{ for some $x$}\}\vspace*{-2mm} \] is a partial Latin cube of order~$n$. \end{lemma} Note that $L_1\circ L_2$ is a Latin cube whenever $L_1$ and $L_2$ are Latin squares. If a partial Latin square $L$ of order $n$ has a subset of $m$ rows and $m$ columns such that the $m^2$ cells defined by these rows and columns form a Latin square of order~$m$, then these cells are said to form a {\em Latin subsquare} of~$L$. We define a {\em Latin subcube} similarly. \begin{corollary} Let $L_1$ and $L_2$ be partial Latin squares sharing the same subsquare $M$ of order $m$ (on the same set of $m^2$ cells). Then $L_1\circ L_2$ contains a Latin subcube of order~$m$. Moreover, if $L_2$ is itself a Latin square, then the stacks of $L_1\circ L_2$ corresponding to the subsquare $M$ are full. \label{fullness} \end{corollary} \begin{lemma} Let $L_1$ be a maximal partial Latin square of order $n$ and size $t$ and let $L_2$ be any Latin square of order~$n$. Then $L_1\circ L_2$ is a maximal partial Latin cube of order $n$ and size~$nt$. \label{cycly} \end{lemma} \begin{proof} Each layer of $L_1\circ L_2$ is the maximal partial Latin square $L_1$ with the symbols relabeled. Hence, $L_1\circ L_2$ is a maximal partial Latin cube. \qquad\end{proof} We can determine certain subintervals of~$ML(3,n)$ by modifying the construction in Lemma~\ref{cycly}. \begin{lemma} %Let $n$ be even. Suppose that some maximal partial Latin square $L$ of order~$n$ and size~$t$ contains a Latin subsquare $M$ of order $\lfloor n/2\rfloor$ and suppose there exists a set $S$ of $\beta$ distinct elements $(r_i,c_i,s_i)$, $i\in [\beta]$, each in $M$ and $2\beta$ distinct empty cells $(r_i,c_i'),(r_i',c_i)$, $i\in [\beta]$, of $L$ such that \[ (L\setminus S)\cup \{(r_i,c_i',s_i),(r_i',c_i,s_i)\mid i\in [\beta]\} \] is a partial Latin square of order~$n$. Then there exists a maximal partial Latin cube of order~$n$ and any size~$t'$, where $tn\leq t'\leq tn+\beta\lfloor n/2\rfloor$. \label{gene} \end{lemma} \begin{proof} Let $N = \lfloor n/2\rfloor$. Without loss of generality, $M$ is a subsquare on the first $N$ rows, columns and symbols. We construct a partial Latin cube $L'$ of order $n$ as follows. Let $L_1$ be the partial Latin square~$L$ containing the Latin subsquare~$M$. Since $M$ has order $N\leq n/2$, Theorem~1.42 of \cite{CDW} implies that $M$ is contained in some Latin square~$L_2$ of order $n$. We now set $L'=L_1\circ L_2$. %We may assume, without loss of generality, that $M$ is a Latin square on entry set $[N]$. By Lemma~\ref{cycly} and Corollary~\ref{fullness}, the partial Latin cube $L'$ is maximal and contains a Latin subcube of order~$N$. Now, let $i\in [\beta]$ and let $(r_i,c_i,s_i)$ be one of the $\beta$ elements of~$M$ satisfying the conditions of the lemma. Let $\ell\in [N]$ and suppose that $(\ell,r_i,c_i,s')\in L'$. By construction, $s'\in [N]$. Next, modify $L'$ by removing $s'$ from cell $(\ell,r_i,c_i)$ and placing $s'$ in cells $(\ell,r_i,c_i')$ and $(\ell,r_i',c_i)$ of layer~$\ell$. The empty cell created cannot be filled with a symbol from~$[N]$ (due to filled cells within layer~$\ell$); nor can it be filled with a symbol from $[n]\setminus [N]$ (due to filled cells in layers from $[n]\setminus [N]$). %(since $L_2$ is a Latin square, %each stack of $L'$ corresponding to a cell from $M$ is full by Lemma~\ref{fullness}). Thus, the resultant partial Latin cube is maximal and has size one more than~$L'$. Moreover we may repeat this operation for any $i\in [\beta]$ and any layer $\ell\in [N]$. The result follows. \qquad\end{proof} We illustrate the previous lemma in the case $n=5$. The partial Latin square $L_1$ is given below with the elements of $S$ in italics; for each $(r_i,c_i,s_i)\in S$, we let $r_i'=r_i+2$ and $c_i'=c_i+2$. The partial Latin square formed by replacing every element of $S$ by two elements is given by $L_1'$. By the above lemma, this guarantees the existence of maximal partial Latin cubes of order $5$ and sizes $65,\ldots,73$. \[ \begin{array}{|c|c|c|c|c|}\hline \!{\it1}\! & \!{\it2}\! & & & \\\hline \!{\it2}\! & \!{\it1}\! & & & \\\hline & & 3 & 4 & 5 \\\hline & & 4 & 5 & 3 \\\hline & & 5 & 3 & 4 \\\hline \multicolumn{5}{c}{}\\[-3mm] \multicolumn{5}{c}{L_1} \end{array} \quad \begin{array}{|c|c|c|c|c|}\hline & & 1 & 2 & \\\hline & & 2 & 1 & \\\hline 1 & 2 & 3 & 4 & 5 \\\hline 2 & 1 & 4 & 5 & 3 \\\hline & & 5 & 3 & 4 \\\hline \multicolumn{5}{c}{}\\[-3mm] \multicolumn{5}{c}{L_1'} \end{array} \quad \begin{array}{|c|c|c|c|c|}\hline 1 & 2 & 3 & 4 & 5 \\\hline 2 & 1 & 4 & 5 & 3 \\\hline 3 & 4 & 5 & 1 & 2 \\\hline 4 & 5 & 2 & 3 & 1 \\\hline 5 & 3 & 1 & 2 & 4 \\\hline \multicolumn{5}{c}{}\\[-3mm] \multicolumn{5}{c}{L_2} \end{array} \] A maximal partial Latin cube of order $5$ and size $70$ is now constructed as above. {\small \[ \begin{array}{|c|c|c|c|c|}\hline & & 1 & 2 & \\\hline & & 2 & 1 & \\\hline 1 & 2 & 3 & 4 & 5 \\\hline 2 & 1 & 4 & 5 & 3 \\\hline & & 5 & 3 & 4 \\\hline \end{array} \quad \begin{array}{|c|c|c|c|c|}\hline & 1 & 2 & & \\\hline 1 & 2 & & & \\\hline 2 & & 5 & 3 & 4 \\\hline & & 3 & 4 & 5 \\\hline & & 4 & 5 & 3 \\\hline \end{array} \quad \begin{array}{|c|c|c|c|c|}\hline 4 & 5 & & & \\\hline 5 & 4 & & & \\\hline & & 1 & 2 & 3 \\\hline & & 2 & 3 & 1 \\\hline & & 3 & 1 & 2 \\\hline \end{array} \quad \begin{array}{|c|c|c|c|c|}\hline 5 & 3 & & & \\\hline 3 & 5 & & & \\\hline & & 4 & 1 & 2 \\\hline & & 1 & 2 & 4 \\\hline & & 2 & 4 & 1 \\\hline \end{array} \quad \begin{array}{|c|c|c|c|c|}\hline 3 & 4 & & & \\\hline 4 & 3 & & & \\\hline & & 2 & 5 & 1 \\\hline & & 5 & 1 & 2 \\\hline & & 1 & 2 & 5 \\\hline \end{array} \] } The following lemma uses constructions very similar to those in Lemmas~9 and~10 of~\cite{HoRa}. In what follows, an {\em idempotent} Latin square of order $n$ contains symbol $i$ in cell $(i,i)$ for each $i\in [n]$. \begin{lemma} If $n$ is even, then there exists a maximal partial Latin square of order~$n$ and size $n^2/2+2k$ satisfying the conditions of Lemma~$\ref{gene}$, where $0\leq k\leq n^2/4-\beta$ and $\beta\in\{3,4\}$. If $n$ is odd and $n\geq 9$, then there exists a maximal partial Latin square of order~$n$ and size $(n^2+1)/2+2k$ satisfying the conditions of Lemma~$\ref{gene}$, where $\beta=(n-1)/2$ and $0\leq k\leq (n-1)^2/4$. \end{lemma} \begin{proof} %We give a construction of such a Latin square $L$ that is equivalent to that of Lemma 9 of \cite{HoRa}. Let $N=\lfloor n/2 \rfloor$. Let $Q$ be a Latin square of order $N$ on symbol set~$[N]$; this occupies the first $N$ rows and columns of~$L$. If $n$ is odd, then we furthermore require that $Q$ is idempotent; such a Latin square exists for $N\geq 3$ (see, for example, Lemma~1.2 of~\cite{CR}). Let $P$ be a Latin square of order $n-N$ on symbol set $[n]\setminus [N]$. Next, let $P'$ be a partial Latin square of size $k$ which is a subset of~$P$, subject to the following restrictions. If $k$ is even, then $P'$ can be any subset such that $0\leq k\leq n^2/4-4$. If $k$ is odd, then $P'$ must not include the final row or column of $P$, so that $0\leq k\leq (n-1)^2/4$. If cell $(i,j,s)$ is in $P'$, then place symbol $s$ in cells $(i ,j+N)$ and $(i+N,j)$ of $L$ and place symbol $s-N$ in cell $(i+N,j+N)$ of~$L$. Otherwise if $(i,j,s) \in P\setminus P'$, then place symbol $s$ in cell $(i+N,j+N)$ of~$L$. The resultant partial Latin square has the desired properties. In particular, suppose that $n$ is even. Whenever $(i,j,s)\in P\setminus P'$, the element $(i-n/2,j-n/2,s-n/2)\in Q$ can be one of the four elements of~$S$ chosen as in Lemma~\ref{gene}, since, by construction, cells $(i,j-n/2)$ and $(i-n/2,j)$ are empty and neither row $i$ nor column $j$ contain symbol $s-n/2$. For $n$ odd, the $\beta$ elements of $S$ may be any $(i,i,i)\in Q$ where $i\in [N]$; cells $(i,n)$ and $(n,i)$ are always empty and neither row $n$ nor column $n$ contains symbol~$i$. \qquad\end{proof} \begin{corollary} If $n$ is even and $n^3/2\leq t\leq n^3-9n/2$, then there exists a maximal partial Latin cube of order $n$ with $t$ filled cells. If $n$ is odd, $n\geq 9$ and $n(n^2+1)/2\leq t\leq n^3-(3n^2-2n-1)/4$, then there exists a maximal partial Latin cube of order $n$ with $t$ filled cells. \label{fillit} \end{corollary} We now give a maximal partial Latin cube of order $n=6$ and size $26\times 6$ constructed as in the above proof. The symbols in italics can each be used to increase the size of the maximal partial Latin cube by $1$ as described above, yielding maximal partial Latin cubes of sizes $26\times 6,\ldots,26\times 6 + 12 = 28\times 6$. \[ \begin{array}{ccc} \begin{array}{|c|c|c|c|c|c|}\hline 1 & 2 & 3 & 4 & 5 & 6 \\\hline 2 & \!{\it3}\! & \!{\it1}\! & 5 & & \\\hline 3 & \!{\it1}\! & \!{\it2}\! & & & \\\hline 4 & 5 & 6 & 1 & 2 & 3 \\\hline 5 & & & 2 & 6 & 4 \\\hline & & & 6 & 4 & 5 \\\hline \end{array} & \begin{array}{|c|c|c|c|c|c|}\hline 2 & 3 & 1 & 5 & 6 & 4 \\\hline 3 & \!{\it1}\! & \!{\it2}\! & 6 & & \\\hline 1 & \!{\it2}\! & \!{\it3}\! & & & \\\hline 5 & 6 & 4 & 2 & 3 & 1 \\\hline 6 & & & 3 & 4 & 5 \\\hline & & & 4 & 5 & 6 \\\hline \end{array} & \begin{array}{|c|c|c|c|c|c|}\hline 3 & 1 & 2 & 6 & 4 & 5 \\\hline 1 & \!{\it2}\! & \!{\it3}\! & 4 & & \\\hline 2 & \!{\it3}\! & \!{\it1}\! & & & \\\hline 6 & 4 & 5 & 3 & 1 & 2 \\\hline 4 & & & 1 & 5 & 6 \\\hline & & & 5 & 6 & 4 \\\hline \end{array} \\ \\[-2mm] \begin{array}{|c|c|c|c|c|c|}\hline 4 & 5 & 6 & 1 & 2 & 3 \\\hline 5 & 6 & 4 & 2 & & \\\hline 6 & 4 & 5 & & & \\\hline 1 & 2 & 3 & 4 & 5 & 6 \\\hline 2 & & & 5 & 3 & 1 \\\hline & & & 3 & 1 & 2 \\\hline \end{array} & \begin{array}{|c|c|c|c|c|c|}\hline 5 & 6 & 4 & 2 & 3 & 1 \\\hline 6 & 4 & 5 & 3 & & \\\hline 4 & 5 & 6 & & & \\\hline 2 & 3 & 1 & 5 & 6 & 4 \\\hline 3 & & & 6 & 1 & 2 \\\hline & & & 1 & 2 & 3 \\\hline \end{array} & \begin{array}{|c|c|c|c|c|c|}\hline 6 & 4 & 5 & 3 & 1 & 2 \\\hline 4 & 5 & 6 & 1 & & \\\hline 5 & 6 & 4 & & & \\\hline 3 & 1 & 2 & 6 & 4 & 5 \\\hline 1 & & & 4 & 2 & 3 \\\hline & & & 2 & 3 & 1 \\\hline \end{array} \end{array} \] Finally, we consider the part of the spectrum $ML(3,n)$ for which there are relatively few ($O(n^2)$) empty cells. We first focus on even orders. A {\em partial incomplete Latin square} PILS$(n;t_1^{u_1}t_2^{u_2}\dots t_k^{u_k})$ is a partial Latin square of order $n$ such that there exists a partition ${\mathcal P}$ of $[n]$ of type $t_1^{u_1}t_2^{u_2}\dots t_k^{u_k}$ so that for each $P\in {\mathcal P}$, the subarray indexed by the rows and columns of $P$ is empty and each row (column) of $P$ and each column (row) of $[n]\setminus P$ contain each symbol from $[n]\setminus P$ exactly once. A PILS can always be completed to a Latin square of the same order by replacing each empty subarray indexed by $P$ by a Latin square on the symbol set~$P$. \begin{lemma} If $a\geq 3$ and $0\leq b\leq 2$, then there exists a {\rm PILS}$(3^ab^1)$. \label{pils} \end{lemma} \begin{proof} We give a rough sketch of the construction. For $b=0$, take an idempotent Latin square of order $3$, replace each entry with a Latin square of order $a$ and remove the Latin squares on the main diagonal. For $b\in\{1,2\}$, take the construction for $b=0$, making sure that the Latin squares of order~$a$ each possess at least two disjoint transversals. (Such Latin squares exist even for $a=6$; see for example Latin square 6.2 from III.1.3 in~\cite{CDW}.) Choose a set of transversals from the subsquares of order~$a$ so that each row or column contains $b$ entries from a transversal. Add $b$ extra rows and columns. Replace the transversals with entries $3a+1$ (and $3a+2$ if $b=2$), shifting the original entries to the final $b$ rows and columns. \qquad\end{proof} Let $L_1$ be a PILS$(3^ab^1)$ (with the one holes of size $b$ filled in) and let $L_2$ be a completion of $L_1$ to a Latin square. Observe that the partial Latin cube $L_1\circ L_2$ contains $a$ empty $3\times 3\times 3$ subarrays which may be replaced by any $a$ partial Latin cubes of order $3$ (on prescribed symbol sets). Moreover, if each of the inserted partial Latin cubes are maximal, then the overall partial Latin cube will also be maximal. These observations yield the following corollary to Lemma~\ref{pils}. \begin{corollary} Let $27-k_1,27-k_2,\dots,27-k_a\in ML(3,3)$ for $a\geq 3$, and let $b\in\{0,1,2\}$. Then there exists a maximal partial Latin cube of order $3a+b$ with exactly $k_1+k_2+\dots+k_a$ empty cells. \end{corollary} \begin{theorem} Let $n$ and $t$ be integers such that $n=10$ or $n\geq 12$, $3\leq t\leq 9n/2$. Then there exists a maximal partial Latin cube of order $n$ and exactly $n^3-t$ filled cells. \end{theorem} \begin{proof} Let $a=\lfloor n/3\rfloor$ and $b=n-3a$. Now, $ML(3,3)=\{9,12,14,\dots,24,27\}$ by Theorem~\ref{thm:computation} (see Section~\ref{sec:computation}). The theorem holds for $t=18(a-1)+13$ which can be seen by setting $k_1=k_2=\dots =k_{a-1}=18$ and $k_{a}=13$; for lower values of $t$, $k_{a}$ can be replaced by $12$ or $11$ and each other $k_i$ can be replaced by $15$ and so forth. Thus by the previous corollary, it suffices to show that $18(a-1)+13\geq 9n/2$. This is clearly true for $n=10$; also $18(n-2)/3-5=6n-17\geq 9n/2$ for $n\geq 12$. \qquad\end{proof} From Corollary~\ref{fillit} and the previous theorem we obtain the following. \begin{theorem} \label{thm:evencase} Let $n$ and $t$ be integers such that $n$ is even, $n\geq 10$ and $3\leq t\leq n^3/2$. Then there exists a maximal partial Latin cube of order $n$ and exactly $n^3-t$ filled cells. \end{theorem} We next focus on the case in which $n$ is odd. It is well known that there exists a Latin square $L_1$ of order $n$ with a subsquare of order~$m$ for any $n$ and $m$ such that $m\leq \lfloor n/2\rfloor$. Let $L_1'$ be the partial Latin square created by removing this subsquare from~$L_1$. Then $L_1'\circ L_1$ is a partial Latin cube with every entry filled except for a three-dimensional subarray of dimensions $m\times m\times m$. Moreover, we may insert a maximal partial Latin cube of order $m$ into this ``hole'' to create a maximal partial Latin cube of order~$n$. This implies the following lemma. \begin{lemma} If $n\geq 2m$ and some maximal partial Latin cube of order $m$ has $t$ empty cells, then there is a maximal partial Latin cube of order $n$ with $t$ empty cells. \end{lemma} \begin{theorem} \label{thm:oddcase} Let $n$ and $t$ be integers such that $n$ is odd, $n\geq 21$ and $3\leq t\leq n(n^2-1)/2$. Then there exists a maximal partial Latin cube of order $n$ and exactly $n^3-t$ filled cells. \end{theorem} \begin{proof} Let $M=\lfloor n/4\rfloor$. By Theorem~\ref{thm:evencase}, there exists a maximal partial Latin cube of order $2M$ with $t$ empty cells, for any $t$ with $3\leq t\leq 4M^3$. Thus by the previous lemma, there exists a maximal partial Latin cube of order $n$ with $t$ empty cells. Since $M\geq (n-3)/4$, Corollary~\ref{fillit} implies that it suffices to show that \[ 4\left(\frac{n-3}{4}\right)^3\geq \frac{3n^2-2n-1}{4} \] which is certainly true for $n\geq 21$. \qquad\end{proof} \newpage \section*{Appendix} \label{sec:appendix} Below are examples of maximal partial Latin cubes for each of the spectrum values given in Theorem~\ref{thm:computation}. \psset{linearc=0,fillcolor=white,gridcolor=black,gridlabelcolor=white,subgriddiv=1} \newcommand{\dcube}[2]{\psset{unit=4mm} \begin{pspicture}(0,0)(2,2)\rput(.5,1.5){#1} \rput(.5, .5){#2} \psgrid(0,0)(2,2)\end{pspicture}} \newcommand{\dcuba}[2]{\begin{pspicture}(0,0)(0,0)\rput(0,0){#1}\rput(1,0){#2}\end{pspicture}} \newcommand{\tcube}[3]{\psset{unit=4mm} \begin{pspicture}(0,0)(3,3)\rput(.5,2.5){#1} \rput(.5,1.5){#2} \rput(.5, .5){#3} \psgrid(0,0)(3,3)\end{pspicture}} \newcommand{\tcuba}[3]{\begin{pspicture}(0,0)(0,0)\rput(0,0){#1}\rput(1,0){#2}\rput(2,0){#3}\end{pspicture}} \newcommand{\qcube}[4]{\psset{unit=2.6mm} \begin{pspicture}(0,0)(4,4)\rput(.5,3.5){#1} \rput(.5,2.5){#2} \rput(.5,1.5){#3} \rput(.5, .5){#4} \psgrid(0,0)(4,4)\end{pspicture}} \newcommand{\qcuba}[4]{\begin{pspicture}(0,0)(0,0)\rput(0,0){#1}\rput(1,0){#2}\rput(2,0){#3}\rput(3,0){#4}\end{pspicture}} \newcommand{\myhhspace}{\hspace*{8mm}} \newcommand{\myhspace}{\hspace*{3mm}} \newcommand{\myvspace}{\\[2mm]} \[ \dcube{\dcuba{1}{ }} {\dcuba{ }{2}} \myhspace \dcube{\dcuba{ }{2}} {\dcuba{1}{ }} \hspace*{15mm} \dcube{\dcuba{1}{ }} {\dcuba{ }{2}} \myhspace \dcube{\dcuba{2}{1}} {\dcuba{1}{ }} \hspace*{15mm} \dcube{\dcuba{1}{2}} {\dcuba{2}{1}} \myhspace \dcube{\dcuba{2}{1}} {\dcuba{1}{2}} \myvspace \] \[ \begin{array}{c} % t = 9 \tcube{\tcuba{1}{ }{ }} {\tcuba{ }{2}{ }} {\tcuba{ }{ }{3}} \myhspace \tcube{\tcuba{ }{3}{ }} {\tcuba{ }{ }{1}} {\tcuba{2}{ }{ }} \myhspace \tcube{\tcuba{ }{ }{2}} {\tcuba{3}{ }{ }} {\tcuba{ }{1}{ }} \hspace*{15mm} % t = 12 \tcube{\tcuba{1}{2}{ }} {\tcuba{3}{1}{ }} {\tcuba{ }{ }{2}} \myhspace \tcube{\tcuba{2}{1}{ }} {\tcuba{ }{ }{1}} {\tcuba{ }{3}{ }} \myhspace \tcube{\tcuba{ }{ }{3}} {\tcuba{ }{2}{ }} {\tcuba{1}{ }{ }} \\\\ % t = 14 \tcube{\tcuba{1}{2}{3}} {\tcuba{2}{1}{ }} {\tcuba{ }{ }{ }} \myhspace \tcube{\tcuba{2}{ }{ }} {\tcuba{1}{2}{ }} {\tcuba{ }{3}{1}} \myhspace \tcube{\tcuba{ }{1}{ }} {\tcuba{ }{ }{3}} {\tcuba{3}{ }{2}} \hspace*{15mm} % t = 15 \tcube{\tcuba{1}{2}{3}} {\tcuba{2}{1}{ }} {\tcuba{3}{ }{2}} \myhspace \tcube{\tcuba{2}{3}{ }} {\tcuba{ }{ }{2}} {\tcuba{1}{ }{3}} \myhspace \tcube{\tcuba{ }{ }{1}} {\tcuba{3}{ }{ }} {\tcuba{ }{2}{ }} \\\\ % t = 16 \tcube{\tcuba{1}{2}{3}} {\tcuba{2}{1}{ }} {\tcuba{3}{ }{2}} \myhspace \tcube{\tcuba{2}{3}{ }} {\tcuba{ }{ }{1}} {\tcuba{ }{1}{ }} \myhspace \tcube{\tcuba{ }{ }{1}} {\tcuba{3}{2}{ }} {\tcuba{2}{ }{3}} \hspace*{15mm} % t = 17 \tcube{\tcuba{1}{2}{3}} {\tcuba{2}{1}{ }} {\tcuba{3}{ }{2}} \myhspace \tcube{\tcuba{2}{3}{1}} {\tcuba{1}{2}{ }} {\tcuba{ }{ }{3}} \myhspace \tcube{\tcuba{ }{ }{ }} {\tcuba{3}{ }{2}} {\tcuba{2}{1}{ }} \\\\ % t = 18 \tcube{\tcuba{1}{2}{3}} {\tcuba{2}{1}{ }} {\tcuba{3}{ }{2}} \myhspace \tcube{\tcuba{2}{3}{1}} {\tcuba{1}{2}{3}} {\tcuba{ }{ }{ }} \myhspace \tcube{\tcuba{ }{ }{ }} {\tcuba{3}{ }{2}} {\tcuba{2}{1}{3}} \hspace*{15mm} % t = 19 \tcube{\tcuba{1}{2}{3}} {\tcuba{2}{1}{ }} {\tcuba{3}{ }{2}} \myhspace \tcube{\tcuba{2}{3}{1}} {\tcuba{1}{2}{3}} {\tcuba{ }{1}{ }} \myhspace \tcube{\tcuba{3}{1}{ }} {\tcuba{ }{ }{2}} {\tcuba{1}{3}{ }} \\\\ % t = 20 \tcube{\tcuba{1}{2}{3}} {\tcuba{2}{1}{ }} {\tcuba{3}{ }{2}} \myhspace \tcube{\tcuba{2}{3}{1}} {\tcuba{1}{2}{3}} {\tcuba{ }{1}{ }} \myhspace \tcube{\tcuba{3}{1}{2}} {\tcuba{ }{3}{ }} {\tcuba{2}{ }{1}} \hspace*{15mm} % t = 20 \tcube{\tcuba{1}{2}{3}} {\tcuba{2}{1}{ }} {\tcuba{3}{ }{2}} \myhspace \tcube{\tcuba{2}{3}{1}} {\tcuba{1}{2}{3}} {\tcuba{ }{1}{ }} \myhspace \tcube{\tcuba{3}{1}{2}} {\tcuba{ }{3}{1}} {\tcuba{2}{ }{3}} \\\\ % t = 22 \tcube{\tcuba{1}{2}{3}} {\tcuba{2}{1}{ }} {\tcuba{3}{ }{2}} \myhspace \tcube{\tcuba{2}{3}{1}} {\tcuba{1}{2}{3}} {\tcuba{ }{1}{ }} \myhspace \tcube{\tcuba{3}{1}{2}} {\tcuba{ }{3}{1}} {\tcuba{1}{2}{3}} \hspace*{15mm} % t = 23 \tcube{\tcuba{1}{2}{3}} {\tcuba{2}{1}{ }} {\tcuba{3}{ }{2}} \myhspace \tcube{\tcuba{2}{3}{1}} {\tcuba{3}{ }{2}} {\tcuba{ }{1}{3}} \myhspace \tcube{\tcuba{3}{1}{2}} {\tcuba{1}{2}{3}} {\tcuba{2}{3}{1}} \\\\ % t = 24 \tcube{\tcuba{1}{2}{3}} {\tcuba{2}{1}{ }} {\tcuba{3}{ }{2}} \myhspace \tcube{\tcuba{2}{3}{1}} {\tcuba{3}{ }{2}} {\tcuba{1}{2}{3}} \myhspace \tcube{\tcuba{3}{1}{2}} {\tcuba{1}{2}{3}} {\tcuba{2}{3}{1}} \hspace*{15mm} % t = 27 \tcube{\tcuba{1}{2}{3}} {\tcuba{2}{3}{1}} {\tcuba{3}{1}{2}} \myhspace \tcube{\tcuba{2}{3}{1}} {\tcuba{3}{1}{2}} {\tcuba{1}{2}{3}} \myhspace \tcube{\tcuba{3}{1}{2}} {\tcuba{1}{2}{3}} {\tcuba{2}{3}{1}} \end{array} \] {\scriptsize \[ \begin{array}{c} % t = 31 \qcube{\qcuba{ }{1}{2}{3}} {\qcuba{4}{ }{ }{ }} {\qcuba{ }{ }{1}{2}} {\qcuba{ }{3}{ }{1}} \myhspace \qcube{\qcuba{ }{ }{1}{2}} {\qcuba{ }{4}{ }{ }} {\qcuba{3}{ }{2}{1}} {\qcuba{2}{ }{ }{3}} \myhspace \qcube{\qcuba{ }{3}{ }{1}} {\qcuba{ }{ }{4}{ }} {\qcuba{2}{ }{ }{3}} {\qcuba{3}{1}{ }{2}} \myhspace \qcube{\qcuba{4}{ }{ }{ }} {\qcuba{1}{2}{3}{4}} {\qcuba{ }{4}{ }{ }} {\qcuba{ }{ }{4}{ }} \myhhspace % t = 32 \qcube{\qcuba{4}{3}{1}{ }} {\qcuba{ }{1}{ }{2}} {\qcuba{ }{4}{ }{ }} {\qcuba{3}{ }{4}{ }} \myhspace \qcube{\qcuba{ }{1}{2}{ }} {\qcuba{4}{ }{3}{ }} {\qcuba{ }{ }{1}{3}} {\qcuba{ }{2}{ }{1}} \myhspace \qcube{\qcuba{ }{4}{ }{ }} {\qcuba{ }{ }{2}{3}} {\qcuba{2}{ }{3}{1}} {\qcuba{1}{ }{ }{2}} \myhspace \qcube{\qcuba{3}{ }{ }{4}} {\qcuba{ }{2}{1}{ }} {\qcuba{1}{ }{2}{ }} {\qcuba{2}{3}{ }{ }} \myvspace % t = 33 \qcube{\qcuba{2}{1}{3}{ }} {\qcuba{ }{ }{1}{4}} {\qcuba{ }{2}{ }{1}} {\qcuba{3}{ }{2}{ }} \myhspace \qcube{\qcuba{4}{ }{2}{ }} {\qcuba{1}{ }{3}{ }} {\qcuba{3}{ }{ }{2}} {\qcuba{ }{4}{1}{ }} \myhspace \qcube{\qcuba{ }{3}{ }{1}} {\qcuba{4}{2}{ }{ }} {\qcuba{ }{1}{4}{ }} {\qcuba{2}{ }{ }{3}} \myhspace \qcube{\qcuba{ }{2}{1}{3}} {\qcuba{ }{3}{2}{ }} {\qcuba{4}{ }{ }{ }} {\qcuba{ }{ }{3}{1}} \myhhspace % t = 34 \qcube{\qcuba{3}{4}{ }{2}} {\qcuba{4}{3}{ }{ }} {\qcuba{ }{1}{2}{ }} {\qcuba{ }{2}{1}{ }} \myhspace \qcube{\qcuba{1}{3}{2}{ }} {\qcuba{2}{ }{3}{1}} {\qcuba{4}{ }{ }{3}} {\qcuba{ }{ }{ }{4}} \myhspace \qcube{\qcuba{ }{ }{4}{1}} {\qcuba{1}{ }{ }{2}} {\qcuba{ }{2}{1}{ }} {\qcuba{3}{1}{ }{ }} \myhspace \qcube{\qcuba{2}{ }{1}{ }} {\qcuba{ }{4}{ }{ }} {\qcuba{3}{ }{ }{4}} {\qcuba{1}{ }{2}{3}} \myvspace % t = 35 \qcube{\qcuba{3}{4}{ }{1}} {\qcuba{1}{ }{3}{2}} {\qcuba{ }{2}{1}{ }} {\qcuba{4}{1}{ }{ }} \myhspace \qcube{\qcuba{4}{3}{ }{2}} {\qcuba{3}{ }{4}{ }} {\qcuba{ }{1}{2}{ }} {\qcuba{ }{2}{1}{ }} \myhspace \qcube{\qcuba{2}{ }{1}{ }} {\qcuba{ }{4}{ }{ }} {\qcuba{3}{ }{ }{4}} {\qcuba{1}{ }{2}{3}} \myhspace \qcube{\qcuba{1}{ }{2}{ }} {\qcuba{2}{ }{ }{1}} {\qcuba{4}{ }{ }{3}} {\qcuba{ }{3}{ }{4}} \myhhspace % t = 36 \qcube{\qcuba{4}{2}{ }{1}} {\qcuba{1}{ }{4}{3}} {\qcuba{ }{3}{1}{ }} {\qcuba{2}{1}{ }{ }} \myhspace \qcube{\qcuba{ }{4}{2}{3}} {\qcuba{4}{ }{ }{2}} {\qcuba{ }{1}{3}{ }} {\qcuba{ }{3}{1}{ }} \myhspace \qcube{\qcuba{1}{ }{3}{ }} {\qcuba{3}{ }{2}{1}} {\qcuba{2}{ }{ }{4}} {\qcuba{ }{4}{ }{2}} \myhspace \qcube{\qcuba{3}{ }{1}{ }} {\qcuba{ }{2}{ }{ }} {\qcuba{4}{ }{ }{2}} {\qcuba{1}{ }{3}{4}} \myvspace % t = 37 \qcube{\qcuba{3}{ }{2}{1}} {\qcuba{4}{1}{ }{2}} {\qcuba{1}{ }{ }{3}} {\qcuba{2}{4}{3}{ }} \myhspace \qcube{\qcuba{2}{4}{1}{ }} {\qcuba{1}{ }{3}{ }} {\qcuba{ }{2}{ }{4}} {\qcuba{ }{1}{2}{3}} \myhspace \qcube{\qcuba{1}{3}{ }{ }} {\qcuba{3}{ }{1}{4}} {\qcuba{ }{ }{4}{2}} {\qcuba{4}{2}{ }{ }} \myhspace \qcube{\qcuba{ }{ }{4}{2}} {\qcuba{ }{3}{2}{ }} {\qcuba{3}{1}{ }{ }} {\qcuba{ }{ }{ }{1}} \myhhspace % t = 38 \qcube{\qcuba{2}{4}{ }{ }} {\qcuba{4}{3}{1}{ }} {\qcuba{1}{2}{ }{3}} {\qcuba{3}{1}{2}{ }} \myhspace \qcube{\qcuba{4}{1}{ }{3}} {\qcuba{1}{4}{ }{ }} {\qcuba{3}{ }{2}{1}} {\qcuba{ }{ }{1}{2}} \myhspace \qcube{\qcuba{1}{3}{2}{ }} {\qcuba{ }{ }{3}{2}} {\qcuba{4}{1}{ }{ }} {\qcuba{2}{ }{ }{4}} \myhspace \qcube{\qcuba{ }{ }{3}{1}} {\qcuba{ }{2}{ }{3}} {\qcuba{ }{ }{4}{2}} {\qcuba{1}{3}{ }{ }} \myvspace % t = 39 \qcube{\qcuba{2}{3}{ }{1}} {\qcuba{3}{ }{1}{4}} {\qcuba{4}{ }{3}{ }} {\qcuba{ }{1}{4}{2}} \myhspace \qcube{\qcuba{3}{1}{ }{2}} {\qcuba{2}{ }{4}{1}} {\qcuba{1}{2}{ }{ }} {\qcuba{ }{ }{1}{4}} \myhspace \qcube{\qcuba{1}{2}{ }{4}} {\qcuba{4}{3}{ }{ }} {\qcuba{3}{4}{ }{2}} {\qcuba{ }{ }{2}{1}} \myhspace \qcube{\qcuba{4}{ }{3}{ }} {\qcuba{1}{2}{ }{ }} {\qcuba{2}{ }{1}{3}} {\qcuba{ }{3}{ }{ }} \myhhspace % t = 40 \qcube{\qcuba{3}{2}{ }{1}} {\qcuba{2}{1}{ }{4}} {\qcuba{1}{4}{ }{2}} {\qcuba{4}{ }{3}{ }} \myhspace \qcube{\qcuba{2}{1}{3}{ }} {\qcuba{1}{3}{ }{2}} {\qcuba{3}{2}{ }{4}} {\qcuba{ }{ }{2}{1}} \myhspace \qcube{\qcuba{1}{3}{4}{ }} {\qcuba{3}{2}{ }{ }} {\qcuba{2}{ }{1}{ }} {\qcuba{ }{1}{ }{3}} \myhspace \qcube{\qcuba{4}{ }{ }{2}} {\qcuba{ }{ }{4}{1}} {\qcuba{ }{3}{2}{ }} {\qcuba{3}{4}{1}{ }} \myvspace % t = 41 \qcube{\qcuba{3}{2}{ }{1}} {\qcuba{2}{1}{ }{4}} {\qcuba{1}{4}{ }{2}} {\qcuba{4}{ }{3}{ }} \myhspace \qcube{\qcuba{2}{1}{3}{4}} {\qcuba{1}{3}{ }{2}} {\qcuba{3}{ }{4}{ }} {\qcuba{ }{2}{ }{1}} \myhspace \qcube{\qcuba{1}{3}{4}{ }} {\qcuba{3}{2}{ }{ }} {\qcuba{2}{ }{1}{ }} {\qcuba{ }{1}{2}{3}} \myhspace \qcube{\qcuba{4}{ }{ }{2}} {\qcuba{ }{4}{2}{1}} {\qcuba{ }{3}{ }{4}} {\qcuba{3}{ }{1}{ }} \myhhspace % t = 42 \qcube{\qcuba{3}{1}{ }{2}} {\qcuba{1}{2}{ }{4}} {\qcuba{2}{4}{ }{1}} {\qcuba{4}{ }{3}{ }} \myhspace \qcube{\qcuba{1}{2}{3}{4}} {\qcuba{2}{3}{ }{1}} {\qcuba{3}{1}{ }{ }} {\qcuba{ }{ }{4}{2}} \myhspace \qcube{\qcuba{2}{3}{4}{ }} {\qcuba{3}{1}{ }{ }} {\qcuba{1}{ }{2}{ }} {\qcuba{ }{2}{1}{3}} \myhspace \qcube{\qcuba{4}{ }{ }{1}} {\qcuba{ }{4}{1}{2}} {\qcuba{ }{3}{ }{4}} {\qcuba{3}{1}{2}{ }} \myvspace % t = 43 \qcube{\qcuba{3}{1}{4}{2}} {\qcuba{1}{2}{ }{4}} {\qcuba{2}{4}{ }{1}} {\qcuba{4}{ }{3}{ }} \myhspace \qcube{\qcuba{1}{2}{3}{ }} {\qcuba{2}{3}{4}{1}} {\qcuba{3}{1}{ }{ }} {\qcuba{ }{4}{ }{2}} \myhspace \qcube{\qcuba{2}{3}{ }{4}} {\qcuba{3}{1}{ }{ }} {\qcuba{1}{ }{2}{ }} {\qcuba{ }{2}{1}{3}} \myhspace \qcube{\qcuba{4}{ }{ }{1}} {\qcuba{ }{4}{1}{2}} {\qcuba{ }{3}{ }{4}} {\qcuba{3}{1}{2}{ }} \myhhspace % t = 44 \qcube{\qcuba{3}{2}{4}{1}} {\qcuba{2}{3}{1}{ }} {\qcuba{1}{4}{3}{2}} {\qcuba{ }{1}{2}{4}} \myhspace \qcube{\qcuba{1}{3}{2}{ }} {\qcuba{3}{1}{ }{4}} {\qcuba{2}{ }{ }{1}} {\qcuba{ }{4}{1}{3}} \myhspace \qcube{\qcuba{2}{1}{ }{3}} {\qcuba{1}{2}{ }{ }} {\qcuba{3}{ }{4}{ }} {\qcuba{4}{ }{3}{1}} \myhspace \qcube{\qcuba{4}{ }{1}{2}} {\qcuba{ }{ }{4}{3}} {\qcuba{ }{3}{2}{4}} {\qcuba{2}{ }{ }{ }} \myvspace % t = 45 \qcube{\qcuba{2}{1}{4}{3}} {\qcuba{1}{2}{ }{ }} {\qcuba{3}{ }{1}{4}} {\qcuba{4}{ }{3}{1}} \myhspace \qcube{\qcuba{3}{2}{ }{1}} {\qcuba{2}{3}{1}{ }} {\qcuba{1}{4}{ }{2}} {\qcuba{ }{1}{2}{4}} \myhspace \qcube{\qcuba{1}{3}{2}{ }} {\qcuba{3}{1}{ }{4}} {\qcuba{2}{ }{3}{1}} {\qcuba{ }{4}{1}{3}} \myhspace \qcube{\qcuba{4}{ }{1}{2}} {\qcuba{ }{4}{ }{3}} {\qcuba{ }{3}{2}{ }} {\qcuba{2}{ }{4}{ }} \myhhspace % t = 46 \qcube{\qcuba{3}{1}{ }{2}} {\qcuba{1}{3}{2}{ }} {\qcuba{2}{4}{1}{ }} {\qcuba{4}{2}{ }{1}} \myhspace \qcube{\qcuba{2}{3}{4}{1}} {\qcuba{3}{2}{1}{ }} {\qcuba{1}{ }{ }{3}} {\qcuba{ }{1}{3}{4}} \myhspace \qcube{\qcuba{1}{2}{3}{ }} {\qcuba{2}{1}{ }{4}} {\qcuba{3}{ }{2}{1}} {\qcuba{ }{4}{1}{2}} \myhspace \qcube{\qcuba{4}{ }{1}{3}} {\qcuba{ }{4}{ }{2}} {\qcuba{ }{1}{3}{4}} {\qcuba{3}{ }{2}{ }} \myvspace % t = 47 \qcube{\qcuba{2}{1}{3}{4}} {\qcuba{1}{2}{4}{ }} {\qcuba{3}{4}{1}{ }} {\qcuba{4}{3}{ }{1}} \myhspace \qcube{\qcuba{3}{2}{4}{1}} {\qcuba{2}{3}{1}{ }} {\qcuba{1}{ }{3}{2}} {\qcuba{ }{1}{2}{ }} \myhspace \qcube{\qcuba{1}{3}{2}{ }} {\qcuba{3}{1}{ }{4}} {\qcuba{2}{ }{4}{1}} {\qcuba{ }{4}{1}{3}} \myhspace \qcube{\qcuba{4}{ }{1}{2}} {\qcuba{ }{4}{ }{3}} {\qcuba{ }{1}{2}{ }} {\qcuba{2}{ }{3}{4}} \myhhspace % t = 48 \qcube{\qcuba{1}{2}{3}{4}} {\qcuba{2}{1}{4}{ }} {\qcuba{3}{4}{ }{1}} {\qcuba{4}{3}{2}{ }} \myhspace \qcube{\qcuba{4}{3}{1}{ }} {\qcuba{3}{4}{ }{2}} {\qcuba{1}{2}{3}{ }} {\qcuba{2}{1}{ }{4}} \myhspace \qcube{\qcuba{2}{4}{ }{3}} {\qcuba{4}{3}{1}{ }} {\qcuba{ }{1}{2}{4}} {\qcuba{1}{ }{3}{2}} \myhspace \qcube{\qcuba{3}{1}{ }{2}} {\qcuba{1}{2}{ }{3}} {\qcuba{2}{3}{4}{ }} {\qcuba{ }{4}{ }{1}} \myvspace % t = 49 \qcube{\qcuba{2}{3}{4}{1}} {\qcuba{3}{2}{1}{4}} {\qcuba{4}{1}{ }{2}} {\qcuba{1}{4}{3}{ }} \myhspace \qcube{\qcuba{4}{2}{ }{3}} {\qcuba{2}{3}{4}{1}} {\qcuba{3}{4}{1}{ }} {\qcuba{ }{1}{ }{2}} \myhspace \qcube{\qcuba{1}{4}{2}{ }} {\qcuba{4}{1}{ }{3}} {\qcuba{2}{3}{ }{1}} {\qcuba{3}{2}{4}{ }} \myhspace \qcube{\qcuba{3}{1}{ }{4}} {\qcuba{1}{4}{2}{ }} {\qcuba{ }{2}{3}{ }} {\qcuba{2}{ }{1}{3}} \myhhspace % t = 50 \qcube{\qcuba{3}{4}{1}{2}} {\qcuba{4}{3}{2}{1}} {\qcuba{1}{2}{ }{3}} {\qcuba{2}{1}{4}{ }} \myhspace \qcube{\qcuba{1}{3}{ }{4}} {\qcuba{3}{4}{1}{2}} {\qcuba{4}{1}{2}{ }} {\qcuba{ }{2}{ }{3}} \myhspace \qcube{\qcuba{2}{1}{3}{ }} {\qcuba{1}{2}{ }{4}} {\qcuba{3}{4}{1}{ }} {\qcuba{4}{3}{ }{2}} \myhspace \qcube{\qcuba{4}{2}{ }{1}} {\qcuba{2}{1}{3}{ }} {\qcuba{ }{3}{4}{2}} {\qcuba{3}{ }{1}{4}} \myvspace % t = 51 \qcube{\qcuba{3}{4}{1}{2}} {\qcuba{4}{3}{2}{1}} {\qcuba{1}{2}{ }{3}} {\qcuba{2}{1}{4}{ }} \myhspace \qcube{\qcuba{2}{1}{3}{ }} {\qcuba{1}{2}{ }{4}} {\qcuba{3}{4}{1}{2}} {\qcuba{4}{3}{2}{1}} \myhspace \qcube{\qcuba{1}{3}{ }{4}} {\qcuba{3}{4}{1}{2}} {\qcuba{4}{1}{2}{ }} {\qcuba{ }{2}{ }{3}} \myhspace \qcube{\qcuba{4}{2}{ }{1}} {\qcuba{2}{1}{3}{ }} {\qcuba{ }{3}{4}{ }} {\qcuba{3}{ }{1}{4}} \myhhspace % t = 52 \qcube{\qcuba{2}{1}{3}{4}} {\qcuba{1}{2}{4}{3}} {\qcuba{3}{4}{2}{ }} {\qcuba{4}{3}{ }{1}} \myhspace \qcube{\qcuba{3}{2}{4}{1}} {\qcuba{2}{1}{ }{ }} {\qcuba{4}{3}{1}{2}} {\qcuba{1}{4}{3}{ }} \myhspace \qcube{\qcuba{1}{3}{2}{ }} {\qcuba{3}{4}{ }{1}} {\qcuba{2}{1}{3}{4}} {\qcuba{ }{2}{1}{3}} \myhspace \qcube{\qcuba{4}{ }{1}{2}} {\qcuba{ }{3}{2}{4}} {\qcuba{1}{2}{4}{3}} {\qcuba{2}{1}{ }{ }} \myvspace % t = 53 \qcube{\qcuba{2}{1}{3}{4}} {\qcuba{1}{2}{4}{3}} {\qcuba{3}{4}{2}{ }} {\qcuba{4}{3}{ }{1}} \myhspace \qcube{\qcuba{3}{2}{4}{1}} {\qcuba{2}{1}{ }{4}} {\qcuba{4}{3}{1}{2}} {\qcuba{1}{4}{3}{ }} \myhspace \qcube{\qcuba{1}{3}{2}{ }} {\qcuba{3}{4}{ }{1}} {\qcuba{2}{1}{3}{4}} {\qcuba{ }{2}{1}{3}} \myhspace \qcube{\qcuba{4}{ }{1}{2}} {\qcuba{ }{3}{2}{ }} {\qcuba{1}{2}{4}{3}} {\qcuba{2}{1}{ }{4}} \myhhspace % t = 54 \qcube{\qcuba{3}{1}{4}{2}} {\qcuba{1}{3}{2}{4}} {\qcuba{4}{2}{3}{ }} {\qcuba{2}{4}{ }{1}} \myhspace \qcube{\qcuba{4}{3}{2}{1}} {\qcuba{3}{1}{ }{2}} {\qcuba{2}{4}{1}{3}} {\qcuba{1}{2}{4}{ }} \myhspace \qcube{\qcuba{1}{4}{3}{ }} {\qcuba{4}{2}{ }{1}} {\qcuba{3}{1}{2}{4}} {\qcuba{ }{3}{1}{2}} \myhspace \qcube{\qcuba{2}{ }{1}{3}} {\qcuba{ }{4}{3}{ }} {\qcuba{1}{3}{4}{2}} {\qcuba{3}{1}{2}{4}} \myvspace % t = 55 \qcube{\qcuba{3}{1}{4}{2}} {\qcuba{1}{3}{2}{ }} {\qcuba{4}{2}{3}{1}} {\qcuba{2}{ }{1}{4}} \myhspace \qcube{\qcuba{4}{3}{2}{1}} {\qcuba{3}{1}{ }{4}} {\qcuba{2}{4}{1}{3}} {\qcuba{1}{2}{4}{ }} \myhspace \qcube{\qcuba{2}{4}{1}{3}} {\qcuba{ }{2}{3}{1}} {\qcuba{1}{3}{2}{4}} {\qcuba{3}{1}{ }{2}} \myhspace \qcube{\qcuba{1}{2}{3}{4}} {\qcuba{4}{ }{1}{2}} {\qcuba{3}{1}{4}{ }} {\qcuba{ }{3}{2}{1}} \myhhspace % t = 56 \qcube{\qcuba{1}{2}{3}{4}} {\qcuba{2}{1}{4}{ }} {\qcuba{3}{4}{2}{1}} {\qcuba{4}{3}{1}{2}} \myhspace \qcube{\qcuba{4}{3}{2}{1}} {\qcuba{3}{4}{1}{ }} {\qcuba{2}{1}{3}{4}} {\qcuba{1}{2}{4}{3}} \myhspace \qcube{\qcuba{2}{1}{4}{3}} {\qcuba{1}{3}{ }{2}} {\qcuba{4}{2}{1}{ }} {\qcuba{3}{ }{2}{4}} \myhspace \qcube{\qcuba{3}{4}{1}{2}} {\qcuba{4}{2}{ }{3}} {\qcuba{1}{3}{4}{ }} {\qcuba{2}{1}{3}{ }} \myvspace % t = 57 \qcube{\qcuba{2}{3}{4}{1}} {\qcuba{3}{2}{1}{4}} {\qcuba{1}{4}{3}{2}} {\qcuba{4}{1}{2}{3}} \myhspace \qcube{\qcuba{3}{2}{1}{ }} {\qcuba{2}{1}{4}{3}} {\qcuba{4}{3}{2}{1}} {\qcuba{1}{ }{3}{4}} \myhspace \qcube{\qcuba{4}{1}{3}{2}} {\qcuba{1}{4}{2}{ }} {\qcuba{3}{2}{1}{ }} {\qcuba{2}{3}{4}{1}} \myhspace \qcube{\qcuba{1}{4}{2}{3}} {\qcuba{4}{3}{ }{1}} {\qcuba{2}{1}{ }{4}} {\qcuba{3}{2}{1}{ }} \myhhspace % t = 58 \qcube{\qcuba{2}{3}{4}{1}} {\qcuba{3}{2}{1}{4}} {\qcuba{1}{4}{3}{2}} {\qcuba{4}{1}{2}{3}} \myhspace \qcube{\qcuba{4}{1}{3}{2}} {\qcuba{1}{4}{2}{ }} {\qcuba{3}{2}{1}{4}} {\qcuba{2}{3}{4}{1}} \myhspace \qcube{\qcuba{3}{2}{1}{ }} {\qcuba{2}{1}{4}{3}} {\qcuba{4}{3}{2}{1}} {\qcuba{1}{ }{3}{4}} \myhspace \qcube{\qcuba{1}{4}{2}{3}} {\qcuba{4}{3}{ }{1}} {\qcuba{2}{1}{4}{ }} {\qcuba{3}{2}{1}{ }} \myvspace % t = 59 \qcube{\qcuba{4}{3}{2}{1}} {\qcuba{3}{4}{1}{2}} {\qcuba{2}{1}{ }{4}} {\qcuba{1}{2}{4}{3}} \myhspace \qcube{\qcuba{1}{2}{3}{4}} {\qcuba{2}{1}{ }{3}} {\qcuba{3}{4}{1}{2}} {\qcuba{4}{3}{2}{1}} \myhspace \qcube{\qcuba{2}{1}{4}{3}} {\qcuba{4}{2}{3}{1}} {\qcuba{1}{3}{2}{ }} {\qcuba{3}{4}{1}{2}} \myhspace \qcube{\qcuba{3}{4}{1}{2}} {\qcuba{1}{3}{4}{ }} {\qcuba{4}{2}{3}{1}} {\qcuba{2}{1}{ }{4}} \myhhspace % t = 60 \qcube{\qcuba{2}{3}{1}{4}} {\qcuba{3}{2}{4}{1}} {\qcuba{1}{4}{3}{2}} {\qcuba{4}{1}{2}{3}} \myhspace \qcube{\qcuba{1}{4}{2}{3}} {\qcuba{4}{1}{3}{2}} {\qcuba{2}{3}{1}{4}} {\qcuba{3}{2}{4}{1}} \myhspace \qcube{\qcuba{3}{2}{4}{1}} {\qcuba{2}{3}{1}{ }} {\qcuba{4}{1}{2}{3}} {\qcuba{1}{ }{3}{4}} \myhspace \qcube{\qcuba{4}{1}{3}{2}} {\qcuba{1}{ }{2}{4}} {\qcuba{3}{2}{4}{1}} {\qcuba{2}{3}{1}{ }} \myvspace % t = 61 \qcube{\qcuba{3}{1}{2}{4}} {\qcuba{1}{3}{4}{2}} {\qcuba{2}{4}{1}{3}} {\qcuba{4}{2}{3}{1}} \myhspace \qcube{\qcuba{2}{4}{3}{1}} {\qcuba{4}{2}{1}{3}} {\qcuba{3}{1}{2}{4}} {\qcuba{1}{3}{4}{2}} \myhspace \qcube{\qcuba{4}{2}{1}{3}} {\qcuba{2}{4}{3}{1}} {\qcuba{1}{3}{4}{2}} {\qcuba{3}{1}{2}{ }} \myhspace \qcube{\qcuba{1}{3}{4}{2}} {\qcuba{3}{1}{2}{ }} {\qcuba{4}{2}{3}{1}} {\qcuba{2}{ }{1}{4}} \myhhspace % t = 64 \qcube{\qcuba{1}{2}{3}{4}} {\qcuba{2}{1}{4}{3}} {\qcuba{3}{4}{2}{1}} {\qcuba{4}{3}{1}{2}} \myhspace \qcube{\qcuba{2}{1}{4}{3}} {\qcuba{1}{2}{3}{4}} {\qcuba{4}{3}{1}{2}} {\qcuba{3}{4}{2}{1}} \myhspace \qcube{\qcuba{3}{4}{1}{2}} {\qcuba{4}{3}{2}{1}} {\qcuba{1}{2}{3}{4}} {\qcuba{2}{1}{4}{3}} \myhspace \qcube{\qcuba{4}{3}{2}{1}} {\qcuba{3}{4}{1}{2}} {\qcuba{2}{1}{4}{3}} {\qcuba{1}{2}{3}{4}} \end{array} \]} \section*{Acknowledgements} We gratefully thank the anonymous referees for their excellent feedback that significantly improved the presentation of this paper. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% % \bibliographystyle{plain} % \bibliography{myBibFile} % If you use BibTeX to create a bibliography % then copy and past the contents of your .bbl file into your .tex file \begin{thebibliography}{10} \bibitem{AnHi83} L.~D.~Anderson and A.~J.~W.~Hilton. \newblock Thank Evans!. \newblock {\em Proc.\ London Math.\ Soc.\ (3)}, 47:507--522, 1983. \bibitem{BCMP} D.~Bryant, N.~Cavenagh, B.~Maenhaut, K.~Pula and I.~M.~Wanless. \newblock Nonextendible Latin cuboids. \newblock {\em SIAM J.~Discrete Math.}, 26:239--249, 2012. %\bibitem{BEMW} %D.~Bryant, J.~Egan, B.~Maenhaut and I.~M.~Wanless. %\newblock Indivisible plexes in Latin squares. %\newblock {\em Des.\ Codes Cryptogr.}, 52:93--105, 2009. \bibitem{CDW} C.~J.~Colbourn, J.~H.~Dinitz and I.~M.~Wanless. \newblock Latin squares. \newblock In {\em Handbook of Combinatorial Designs}, 2nd Edition, C.~J.~Colbourn and J.~H.~Dinitz, eds., pages 135--152. Chapman and Hall/CRC, Boca Raton, 2007. \bibitem{CR} C.~J.~Colbourn and A.~Rosa. \newblock {\em Triple Systems}. \newblock Oxford University Press, New York, 1999. \bibitem{Cr} A.~B.~Cruse. \newblock On the finite completion of partial Latin cubes. \newblock {\em J.~Combinatorial Theory Ser.~A}, 17:112--119, 1974. %\bibitem{CO06} %J.~Cutler and L.-D.~{\"O}hman. %\newblock Latin squares with forbidden entries. %\newblock {\em Electron.\ J.~Combin.}, 13: \#R47, 9~pp, 2006. %\bibitem{DWW} %P.~Danziger, I.~M.~Wanless and B.~S.~Webb. %\newblock Monogamous Latin squares. %\newblock {\em J.~Combin.\ Theory Ser.~A}, 118:796--807, 2011. \bibitem{DeOh2014} T.~Denley and L.-D. \"Ohman. \newblock Extending partial Latin cubes. \newblock {\em Ars Combin.} 113:405--414, 2014. %\bibitem{EW} %J.~Egan and I.~M.~Wanless. %\newblock Latin squares with no small odd plexes. %\newblock {\em J.~Combin.\ Designs}, 16:477--492, 2008. \bibitem{evans60} T.~Evans. \newblock Embedding incomplete Latin squares. \newblock {\em Amer.\ Math.\ Monthly}, 67:958--961, 1960. \bibitem{Fu} \newblock H.-L.~Fu. \newblock On Latin $(n\times n\times (n-2))$-parallelepipeds. \newblock {\em Tamkang J.~Math.}, 17:107--111, 1986. \bibitem{haggkvist78} R.~H{\"a}ggkvist. \newblock A solution to the Evans conjecture for Latin squares of large size. \newblock {\em Colloq. Math. Soc. J{\'a}nos Bolyai}, 18:495--513, 1978. %\bibitem{Hall} %M.~Hall. %\newblock An existence theorem for latin squares. %\newblock {\em Bull.\ Amer.\ Math.\ Soc.}, 51:387--388, 1945. \bibitem{Horak} P.~Hor\'{a}k. \newblock Latin parallelepipeds and cubes. \newblock {\em J.~Combin.\ Theory Ser.~A}, 33:213--214, 1982. \bibitem{HoRa} P.~Hor\'{a}k and A.~Rosa. \newblock Maximal partial Latin squares. \newblock In {\em Graphs, Matrices and Designs}, volume 139 of {\em Lecture Notes in Pure and Appl. Math.}, pages 225--235. Dekker, New York, 1993. \bibitem{Kochol} M.~Kochol. \newblock Latin $(n\times n\times (n-2))$-parallelepipeds not completing to a Latin cube. \newblock {\em Math. Slovaca}, 39:121--125, 1989. \bibitem{Koc95} M.~Kochol. \newblock Relatively narrow Latin parallelepipeds that cannot be extended to a Latin cube. \newblock {\em Ars Combin.}, 40:247--260, 1995. %Kuhl, Jaromy(1-WFL); Denley, Tristan(1-AUSP-NDM) %Some partial Latin cubes and their completions. (English summary) %European J. Combin. 32 (2011), no. 8, 1345–1352. \bibitem{LHC} B.~D.~McKay and I.~M.~Wanless. \newblock A census of small Latin hypercubes. \newblock {\em SIAM J.~Discrete Math.}, 22:719--736, 2008. \bibitem{smetaniuk81} B.~Smetaniuk. \newblock A new construction on Latin squares. I. A proof of the Evans conjecture. \newblock {\em Ars Combin.}, 11:155--172, 1981. %\bibitem{WW06} %I.~M.~Wanless and B.~S.~Webb. %\newblock The existence of Latin squares without orthogonal mates. %\newblock {\em Des.\ Codes Cryptogr.}, 40:131--135, 2006. \end{thebibliography} \end{document} %% end of file `docultex.tex'