Chapter 2 Embedding Latin Rectangles
2.1 Embedding Latin Rectangles
This section looks at a problem closely related to completing partial latin squares. The problem of embedding a latin rectangle. is a latin square.
\[def420\] An latin rectangle on is a complete \(r\times s\) array on \(\Sigma\) with the latin property. An latin rectangle is a pair \((\Sigma,R)\) where \(R\) is an \(r\times s\) latin rectangle on \(\Sigma\).
Figure \[fig430\] shows a \(2\times 3\) latin rectangle on \([5]\).
\[fig430\] \[\left[ \begin{array}{ccc} 1 & 5 & 2 \\ 4 & 2 & 1 \end{array} \right]\]
Perhaps the most obvious interesting question about latin rectangles is whether or not there is a finite \(N\) such that every \(r\times s\) latin rectangle can be embedded in some latin square of order \(N\). The first result in this direction was obtained by Marshall Hall, who showed Hall (1945) that an \(r\times n\) latin rectangle can always be embedded in some latin square of order \(n\).
\[M.Hall @MHALL\] \[thm450\] Every \(r\times n\) latin rectangle can be embedded in some latin square of order \(n\).
Theorem \[thm450\] is proved most simply by induction on \(r\), using P.Hall’s Theorem on systems of distinct representatives to construct an \(r+1\)th row. Rather than give this proof, however, the main technique of this thesis, a common approach for problems of this kind, is now introduced. This technique involves constructing a certain graph \(B\) related to the latin rectangle \(R\) which has the property that a certain type of factorisation of the graph corresponds to a completion of \(R\).
\[def460\] A graph \(G\) is a pair \((V,E)\) of disjoint finite sets which satisfies (\[def460A\]) and (\[def460B\]).
\[def460A\] Every element \(e\in E\) has a unique, not necessarily distinct, pair of ends \(\{v,w\}\subseteq V\).
\[def460B\] If \(\{e,e'\}\subseteq E\) and \(e\neq e'\) then \(e\) and \(e'\) have at most one end in common.
If \(G=(V,E)\) is a graph then \(V=V(G)\) is the vertex-set of \(G\). The elements of \(V\) are the vertices of \(G\). The set \(E=E(G)\) is the edge-set of \(G\) and the elements of \(E\) are the edges of \(G\). An edge whose ends coincide is a loop of \(G\). The set \(\{e\in E(G)\,|\, e=uu\mbox{ for some }u\in V(G)\}\) of all loops of \(G\) is denoted by \(L=L(G)\). An edge of \(G\) with distinct ends is a non-loop edge of \(G\). If \(e\) is an edge of \(G\) with ends \(u\) and \(v\) then \(e\) is denoted by \(uv\).
This definition of a graph is slightly unconventional. According to this definition, a graph can have loops but not multiple edges (distinct edges with the same pair of ends).
\[def463\] A graph \(G\) is simple if and only if \(E(G)\) contains no loops.
A graph \(G\) can be represented by a plane drawing in which each vertex \(v\) is assigned a point \(p(v)\) in the plane and drawn as a solid circular disc centered on \(p(v)\). Points \(p(v),p(w)\) are joined by a line segment if and only if \(v\neq w\) and \(vw\in E(G)\), and a loop with end \(u\) is represented by an ellipse intersecting \(p(u)\). The drawing in Figure \[fig464\] is of a particularly famous simple graph, the Petersen Graph.
The Petersen Graph
\[def465\] The following notation is used for the remainder of this chapter. \[\cR=\Rr=\{\rho_i\,|\,i\in [r]\}\] \[\cC=\Cs=\{\gamma_i\,|\,i\in [s]\}\]
\[def470\] If \(R\) is an \(r\times s\) latin rectangle on \(\Sigma\) then \(B=B(R,\Sigma)\) is the simple graph with vertex-set \(V(B)=\cC\cup\Sigma\) and edge-set \[E(B)=\bigcup_{j\in [n]}\{\gamma_j\sigma_k\,|\,R(i,j)\neq \sigma_k\mbox{ for all } i\in [r] \}\]
In other words \(B(R,\Sigma)\) is the graph obtained by joining \(\gamma_j\) to \(\sigma_k\) if and only if symbol \(\sigma_k\) is missing from the \(j\)th column of \(R\).
\[ex490\] The graph in Figure \[fig480\] is the graph \(B(R,[5])\) for the \(2\times 5\) latin rectangle on \([5]\) in Figure \[fig495\]
\[R=\left[ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 3 & 4 & 5 & 1 & 2 \end{array} \right]\]
\(B(R)\) for \(R\) in Figure \[fig495\]
The important point about \(B(R,\Sigma)\) is that, in general, it is an \((n-r)\)-regular bipartite graph.
\[def500\] If \(G\) is a simple graph then \(G\) has a bipartition \(\{U,W\}\) if and only if \(V(G)=U\cup W\), \(U\cap W=\emptyset\) and \(E(G)\subseteq\{uw\,|\,u\in U,w\in W\}\). A graph \(G\) is bipartite if and only if \(V(G)\) has at least one bipartition.
The graph \(B\) in Figure \[fig480\] is bipartite with bipartition \(\{\cC(5),[5]\}\)
\[def510\] A simple graph \(G\) is -regular if and only if every vertex of \(G\) is the end of exactly \(k\) edges of \(G\).
The bipartite graph \(B\) in Figure \[fig480\] is 3-regular.
How can the \(3\)-regular bipartite graph \(B\) in Figure \[fig480\] be used to help complete the latin rectangle in Example \[ex490\]?
Suppose \(Q\) is a \(3\times 5\) rectangle on \([5]\) with the property that the \(i\)th column of \(Q\) contains no symbol from the \(i\)th column of \(R\). Then the \(5\times 5\) array on \([5]\) whose first two rows coincide with the two rows of \(R\) and whose last three rows coincide with the three rows of \(Q\) is a latin square of order 5 in which \(R\) is embedded.
\[ex520\] If \(R\) is the latin rectangle from Example \[ex490\] then \[Q=\left[ \begin{array}{ccccc} 5 & 1 & 2 & 3 & 4\\ 2 & 3 & 4 & 5 & 1\\ 4 & 5 & 1 & 2 & 3 \end{array}\right]\] is an appropriate latin rectangle and \[\left[ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5\\ 3 & 4 & 5 & 1 & 2\\ 5 & 1 & 2 & 3 & 4\\ 2 & 3 & 4 & 5 & 1\\ 4 & 5 & 1 & 2 & 3 \end{array}\right]\] is the corresponding latin square of order 5.
So \(B\) would be useful if it could be applied to the problem of constructing an appropriate latin rectangle, such as \(Q\). Well, each row of the latin rectangle \(Q\) corresponds to a subgraph of \(B(R)\).
\[def530\] A graph \(H\) is a subgraph of a graph \(G\) if and only if \(V(H)\subseteq V(G)\) and \(E(H)\subseteq E(G)\). The notation \(H\triangleleft G\) means that \(H\) is a subgraph of \(G\).
\[def535\] If \(R\) is an \(r\times s\) latin rectangle on \(\Sigma\) and \(i\in [r]\) then \(N=N(R,\Sigma,i)\) is the simple graph with vertex-set \(V(N)=\cC\cup\Sigma\) and edge-set \(E(N)=\{\gamma_j\sigma_k\,|\, j\in [s]\mbox{ and }R(i,j)=k\}\).
\[ex537\] If \(Q\) is defined as in Example \[ex520\] then the simple graphs \(N_1=N(Q,[5],1)\), \(N_2=N(Q,[5],2)\) and \(N_3=N(Q,[5],3)\) are the simple graphs illustrated in Figure \[fig540\].
\(N(Q,[5],1)\), \(N(Q,[5],2)\) and \(N(Q,[5],3)\) for \(Q\) in Example \[ex520\]
The simple graphs \(N_1\), \(N_2\) and \(N_3\) in Figure \[fig540\] have some obvious properties. Firstly, each is a 1-factor of \(B(R)\).
\[def550\] A -factor of a graph \(G\) is a \(k\)-regular subgraph \(H\triangleleft G\) with the property that \(V(H)=V(G)\).
Secondly, the simple graphs \(N_1\), \(N_2\) and \(N_3\) are mututally edge-disjoint.
\[def560\] Graphs \(G\) and \(H\) are edge-disjoint if and only if \(E(G)\cap E(H)=\emptyset\).
Finally the union of the simple graphs \(N_1\), \(N_2\) and \(N_3\) is the simple graph \(B(R)\).
\[def570\] The union of graphs \(G\) and \(H\) is the graph \(G\cup H\) where \(V(G\cup H)=V(G)\cup V(H)\) and \(E(G\cup H)=E(G)\cup E(H)\).
So the set \(\{N_1, N_2,N_3\}\) decomposes the graph \(B(R)\) into three 1-factors.
\[def580\] A decomposition of a graph \(G\) is a set of mutually edge-disjoint graphs \(\{G_1,G_2,\ldots,G_k\}\) such that \(G=G_1\cup G_2\cup\ldots\cup G_k\). A decomposition of \(G\) into 1-factors is a -factorisation of \(G\).
Conversely, if \(B(R)\) in Figure \[fig480\] has a 1-factorisation \(\{F_1,F_2,F_3\}\) then the \(5\times 5\) array \(L\) on \(\Sigma\) defined by \[L(i,j)=\left\lbrace \begin{array}{cl} R(i,j) &\mbox{ if and only if } (i,j)\in [2]\times [5] \\ \sigma_k & \mbox{ if and only if } (i,j)\in ([5]\backslash [2])\times [5]\mbox{ and } \gamma_j\sigma_k\in E(F_i) \end{array}\right.\] is an embedding of \(R\) in a latin square of order 5. This approach, as we show in Lemma \[lem590\], is easily generalised to construct embeddings of all \(r\times n\) latin rectangles in latin squares of order \(n\).
\[lem590\] If an \(r\times n\) latin rectangle \(R\) on \(\Sigma\) can be embedded in a latin square \(L\) of order \(n\) on \(\Sigma\) and \(Q\) is the \((n-r)\times n\) latin rectangle of order \(n\) defined by \(Q(i,j)=L(r+i,j)\) for all \((i,j)\in [n-r]\times [n]\) then the set \[\{N(Q,\Sigma,1),N(Q,\Sigma,2),\ldots,N(Q,\Sigma,n-r)\}\] is a 1-factorisation of \(B(R)\). Conversely, if \(\{F_1,F_2,\ldots,F_{n-r}\}\) is a 1-factorisation of \(B(R)\) then the array \(L\) of order \(n\) given by \[L(i,j)=\left\lbrace \begin{array}{cll} R(i,j) & \mbox{ if and only if } & (i,j)\in [r]\times [n] \\ \sigma_k & \mbox{ if and only if } & (i,j)\in ([n]\backslash [r])\times [n]{ and } \gamma_j\sigma_k\in E(F_i) \end{array}\right.\] is a latin square of order \(n\) on \(\Sigma\) in which \(R\) is embedded.
Suppose \(R\) can be embedded in \(L\), \(i\in [n-r]\) and \(N_i=N(Q,\Sigma,i)\). Then, by definition \(V(N_i)\) and \(V(B)\) are both equal to \(\cC\cup\Sigma\). Therefore \(N_i\) is a subgraph of \(B=B(R)\) if and only if \(E(N_i)\subseteq E(B)\). By the definition of \(N_i\), \(\gamma_j\sigma_k\in E(N_i)\) if and only if there exists some \(j\in [n]\) such that \(Q(i,j)=\sigma_k\) in which case, as \(L\) is a latin square, \(R(i,j)\neq \sigma_k\) for all \(i\in [r]\). Therefore, by the definition of \(B\), it follows that \(\gamma_j\sigma_k\in E(B)\). Hence \(E(N_i)\subseteq E(B)\).
Now it is shown that \(N_i\) is a 1-factor of \(B=B(R)\). Firstly, every vertex of \(N_i\) is the end of some edge of \(N_i\). If \(\gamma_j\in \cC\) then, as \(L\) is a latin square of order \(n\), there is some \(\sigma_k\in\Sigma\) such that \(L(i,j)=\sigma_k\), in which case, by the definition of \(B\), \(\gamma_j\sigma_k\in E(N_i)\). If \(\sigma_k\in\Sigma\) then, again because \(L\) is a latin square of order \(n\), it follows that there is some \(j\in [n]\) such that \(L(i,j)=\sigma_k\) in which case, by the definition of \(B\), it follows that \(\gamma_j\sigma_k\in E(N_i)\). Now, if \(\gamma_j\sigma_k\in E(N_i)\) and \(\gamma_j\sigma_{k'}\in E(N_i)\) then, by the definition of \(N_i\) it follows that \(Q(i,j)=\sigma_k\) and \(Q(i,j)=\sigma_{k'}\). Therefore, as \(Q\) is an array it follows that \(\sigma_k=\sigma_{k'}\). Hence every vertex \(\gamma_j\in \cC\) is the end of at most one edge of \(N_i\). Conversely, if \(\gamma_j\sigma_k\in E(N_i)\) and \(c_{j'}\sigma_k\in E(N_i)\) then, by the definition of \(N_i\), \(Q(i,j)=Q(i,j')=\sigma_k\). As \(Q\) has the latin property it follows that \(j=j'\). Therefore every vertex \(\sigma_k\in\Sigma\) is the end of at most one edge of \(N_i\). Hence every vertex of \(N_i\) is the end of exactly one edge of \(N_i\) and so, as \(N_i\) is a subgraph of \(B\) and \(V(N_i)=V(B)\), it follows that \(N_i\) is a 1-factor of \(B\).
To show that \(\{N_1,\ldots N_{n-r}\}\) is a 1-factorisation it remains to show that the \(N_i\) are mutually edge-disjoint and their union is the graph \(B\). Firstly, if \(\gamma_j\sigma_k\in E(N_i)\) and \(\gamma_j\sigma_k\in N_I\), then, by definition, \(Q(i,j)=Q(I,j)=\sigma_k\) which, as \(Q\) has the latin property, implies that \(i=I\). Therefore, if \(i\neq I\) it follows that \(E(N_i)\cap E(N_I)=\emptyset\). Finally, if \(\gamma_j\sigma_k\in E(B)\) then, by the definition of \(B\) it follows that \(R(i,j)\neq\sigma_k\) for all \(i\in [r]\). Therefore, as \(L\) is a latin square of order \(n\) it follows that there exists some \(i\in [n]\backslash [r]\) such that \(L(i,j)=\sigma_k\) in which case, by the definition of \(N_i\) it follows that \(\gamma_j\sigma_k\in E(N_i)\).
Now suppose \(F=\{F_i\,|\,i\in [n-r]\}\) is a 1-factorisation of \(B(R)\). Then \(L\) is an array of order \(n\) by definition. \(L\) is complete because \(R\) is complete and because if \((i,j)\in [n]\backslash [r]\times [n]\) then, as \(\gamma_j\sigma_k\in E(N_i)\) it follows that \(L(i,j)=\sigma_k\). Now it follows that \(L\) is a latin square if and only if \(L\) has the latin property.
Firstly, if \((i,k)\in [n]^2\) and \((j,l)\in [n]^2\) then, because \(R\) has the latin property it follows that either \(i\neq k\) and \(j\neq l\) or \(i=k\) and \(j=l\). If \(i\in [r]\), \(k\in [n]\backslash [r]\) and \((j,l)\in [n]^2\) then, as \(i\neq k\), it follows that \(L\) has the latin property only if \(L(i,j)=L(k,l)\) implies \(j\neq l\). If \(L(i,j)=L(k,l)\) then \(R(i,j)=L(k,l)\). Now \(L(k,l)=m\) if and only if \(c_l\sigma_m\in F_k\). Therefore, by the definition of \(B\) it follows that \(R(i',l)\neq m\) for all \(i'\in [r]\) and hence, as \(R(i,j)=m\) it follows that \(l\neq j\).
Finally, if \((i,k)\in ([n]\backslash [r])^2\), \((j,l)\in [n]^2\), \(i\neq k\), \(j\neq l\) and \(L(i,j)=L(k,l)=m\) then, by the definition of \(L\), it follows that \(\gamma_js_m\in F_i\) and \(c_ls_m\in F_k\). If \(i=k\) then, as \(F_i=F_k\) is a 1-factor of \(B\) it follows that \(j=l\). Otherwise \(i\neq k\) and, as \(F\) is a decomposition of \(B\), it follows that \(j\neq l\).
So the problem of embedding an \(r\times n\) latin rectangle \(R\) is identical to the problem of 1-factorising the associated bipartite graph \(B(R)\). The fact that \(B(R)\) always has a 1-factorisation is a consequence of \(B(R)\) being both regular and bipartite. It is not difficult to apply the bipartite graph formulation of P.Hall’s Theorem on systems of distinct representatives to construct a 1-factor of a regular bipartite graph. Then, from the observation that a regular bipartite graph with a 1-factor removed is also regular and bipartite, it follows that \(B(R)\) has a 1-factorisation. However, a different approach is taken here. The approach taken is to use the theory of edge-colourings to construct a 1-factorisation of \(B(R)\). The reason this approach is taken here is because it is closer to the methods used in later chapters of this thesis.
\[def600\] If \(G\) is a graph then a -edge-colouring of is a map \(\phi:E(G)\rightarrow\Sigma\). An edge-colouring of a graph is a pair \((\Sigma,\phi)\) where \(\phi\) is a \(\Sigma\)-edge-colouring of \(G\).
Given a 1-factorisation \(F=\{F_i\,|\,i\in [k]\}\) of a graph \(G\) is it simple to construct a corresponding \(F\)-edge-colouring of \(G\) by putting \(\phi(e)=F_i\) if and only if \(e\in E(F_i)\). The fact that \(F\) is a 1-factorisation of \(G\) is reflected in the fact that if \(e\) and \(e'\) are distinct edges of \(G\) with a common end \(v\) then \(\phi(e)\neq\phi(e')\).
\[def610\] An edge-colouring $(\Sigma,\phi)$ of a graph $G$ is
**proper** if and only if $\phi(e)\neq\phi(e')$ for every pair of edges\(\{e,e'\}\subseteq E(G)\), such that \(e\) and \(e'\) share a common end and \(e\neq e'\).
\[def620\] A -edge-colouring of a graph \(G\) is a proper edge-colouring \((S,\phi)\) where \(|S|=k\). A graph \(G\) is -edge-colourable if and only if there exists a \(k\)-edge-colouring of \(G\).
If a graph \(G\) has a vertex \(v\) which is the end of \(K\) edges of \(G\) then \(G\) is \(k\)-edge-colourable only if \(k\geq K\). The minimal \(k\) such that \(G\) is \(k\)-edge-colourable is a parameter of huge interest to graph theorists.
\[def630\] The chromatic index \(\chi'(G)\) of a graph \(G\) is the unique positive integer \(k\) such that \(G\) is \(k\)-edge-colourable but not \((k-1)\)-edge-colourable.
A remarkable Theorem of König says that a bipartite graph with maximum degree \(\Delta\) has chromatic index \(\Delta\). Consequently a \(k\)-regular bipartite graph is \(k\)-edge-colourable.
\[def640\] The degree of a vertex \(v\) of a simple graph \(G\) is the non-negative integer \(d(v)=d(G,v)=|\{e\in E(G)\,|\,v\mbox{ is an end of } e\}|\). The maximum degree of a graph \(G\) is the non-negative integer \(\Delta=\Delta(G)=max_{v\in V(G)} d(G,v)\).
\[König\] \[thm630\] If \(G\) is bipartite then \(\chi'(G)=\Delta(G)\).
To construct a 1-factorisation of \(B=B(R)\) from a \(\Delta(B)\)-edge-colouring \(\Phi\) of \(B\) the idea is to take the subgraphs of \(B\) induced by the colour classes of the edge-coloured graph \((B,\Phi)\) as the elements, the 1-factors, of the 1-factorisation.
\[def645\] An edge-coloured graph graph \(\mathcal{G}\) is a pair \((G,\Phi)\) where \(G\) is a graph and \(\Phi\) is an edge-colouring of \(G\). \(\mathcal{G}\) is proper if and only if \(\Phi\) is proper and -edge-coloured if and only if \(\Phi\) is a \(k\)-edge-colouring.
\[def650\] The colour class of \(\sigma\) in the edge-coloured graph \(\mathcal{G}=(G,(\Sigma,\phi))\) is the subset \([\sigma]=[\mathcal{G},\sigma]=\{e\in E(G)\,|\,\phi(e)=\sigma\}\).
If \(G\) is \(k\)-regular and \(\mathcal{G}=(G,\Phi)\) is \(k\)-edge-coloured then every colour class of \(\mathcal{G}\) is the edge-set of a 1-factor of \(G\) and the set of colour classes is the set of edge-sets of a 1-factorisation of \(G\).
\[lem670\] If \(\cG=(G,(\Sigma,\phi))\) is a \(k\)-edge-coloured graph and \(G\) is \(k\)-regular then \(\{(V(G),[\cG,\sigma])\,|\, \sigma\in \Sigma\}\) is a 1-factorisation of \(G\).
If \(v\in V(G)\) then, as \(G\) is \(k\)-regular and \(\mathcal{G}\) is \(k\)-edge-coloured, it follows that \(v\) is the end of exactly one edge \(e\in [\cG,\sigma]\) for all \(\sigma\in\Sigma\). Therefore \((V(G),[\sigma])\) is a 1-factor of \(G\) for all \(\sigma\in\Sigma\). If \(e\in [\sigma]\) and \(e\in [\sigma']\) then, by the definition of colour class, it follows that \(\phi(e)=\sigma\) and \(\phi(e)=\sigma'\). Hence \(\sigma=\sigma'\) and therefore \(\{(V(G),[\sigma])\,|\, \sigma\in\Sigma)\}\) is a decomposition of \(G\). Hence \(\{(V(G),[\sigma])\,|\, \sigma\in\Sigma\}\) is a decomposition of \(G\) into 1-factors and therefore, by definition, a 1-factorisation of \(G\).
Lemma \[lem670\] and the simple graph \(B(R)\) are together a powerful enough tool to prove Theorem \[thm450\].
\[M.Hall @MHALL\] Every \(r\times n\) latin rectangle can be embedded in some latin square of order \(n\).
Let \(R\) be an \(r\times n\) latin rectangle on \(\Sigma\) and let \(B=B(R)\) be the corresponding bipartite graph. If \(\gamma_j\in \cC\) then, because there are exactly \(r\) symbols \(\sigma_k\Sigma\) such that \(R(i,j)=\sigma_k\) for some \(i\in [r]\) it follows that there are exactly \(n-r\) symbols \(\sigma_k\in\Sigma\) such that \(R(i,j)\neq \sigma_k\) for all \(i\in [r]\). Therefore, by the definition of \(B\), vertex \(\gamma_j\) is the end of exactly \(n-r\) edges of \(B\). If \(\sigma_k\in\Sigma\) then, because there are exactly \(r\) values \(j\in [n]\) such that \(R(i,j)=\sigma_k\) for some \(i\in [r]\) it follows that there are exactly \(n-r\) values \(j\in [n]\) such that \(R(i,j)\neq \sigma_k\) for all \(i\in [r]\). Therefore, by the definition of \(B\) it follows that \(\sigma_k\) is the end of exactly \(n-r\) edges of \(B\). Hence, as \(V(B)=\cC\cup\Sigma\), \(B\) is \((n-r)\)-regular. Consequently \(\Delta(B)=n-r\) and so, by Theorem \[thm630\], it follows that \(B\) is \((n-r)\)-edge-colourable and hence, by Lemma \[lem670\], \(B\) has a 1-factorisation. Now it follows from Lemma \[lem590\] that \(R\) is can be embedded in a latin square of order \(n\).
In retrospect this may seem an awful lot of work to prove a theorem which can be proved, arguably more simply, by applying P. Hall’s Theorem on systems of distinct representatives. This method has its benefits, though. One of those benefits is that it has been successfully adapted to other closely related problems and it is, in essence, the method which is used in subsequent chapters to prove the central results of this thesis. As a second application this method can be used to prove Theorem \[thm690\], arguably the most important result about embedding latin rectangles, which gives a necessary and sufficient condition for an \(r\times s\) latin rectangle to be embeddable in some latin square of order \(n\).
\[def680\] If \(R\) is \(r\times s\) latin rectangle on \(\Sigma\) then \(R(\sigma)=|\{(i,j)\,|\, (i,j)\in [r]\times [s]\mbox{ and } R(i,j)=\sigma\}|\).
\[Ryser @HJR\] \[thm690\] An \(r\times s\) latin rectangle \(R\) on \(\Sigma\) can be embedded in some latin square of order \(n\) on \(\Sigma\) if and only if \(R(\sigma)\geq r+s-n\) for all \(\sigma\in\Sigma\).
This time, instead of the simple graph \(B\), which encodes the information about which symbols are missing from which columns of a latin rectangle, the graph of most use in proving Ryser’s Theorem is the simple graph \(B^{\star}\) which records the information about which symbols are missing in the rows of a latin rectangle.
\[def700\] If \(R\) is an \(r\times s\) latin rectangle on \(\Sigma\) then \(B^{\star}=B^{\star}(R,\Sigma)\) is the graph with vertex-set \(V(B^{\star})=\cR\cup\Sigma\) and edge-set \[E(B^{\star})=\cup_{j\in [n]}\{\rho_j\sigma_k\,|\, R(i,j)\neq \sigma_k\mbox{ for all } j\in [s]\}\]
\[ex710\] If \(R\) is the \(4\times 6\) latin rectangle on \([8]\) in Figure \[fig715\] then \(B^{\star}(R,[8])\) is the graph in Figure \[fig720\]
\[R= \left[ \begin{array}{cccccc} 1 & 5 & 4 & 3 & 7 & 6 \\ 2 & 1 & 5 & 4 & 3 & 7 \\ 8 & 3 & 2 & 6 & 1 & 4 \\ 4 & 8 & 1 & 2 & 6 & 3 \end{array} \right]\] \[fig715\]
\(B^{\star}(R,[8])\) for \(R\) in Ex \[ex710\]
This time the idea is to use \(B^{\star}\) to help with the problem of embedding \(R\) in a latin square of order \(n\). This problem is made easier by Theorem \[thm450\]. According to Theorem \[thm450\] all that is needed to embed \(R\) in a latin square of order \(n\) is an embedding of \(R\) in a \(r\times n\) latin rectangle on \(\Sigma\). In other words it is sufficient to construct an \(r\times (n-s)\) latin rectangle \(Q\) on \(\Sigma\) with the property that row \(i\) of \(Q\) contains no symbol contained in row \(i\) of \(R\).
\[ex730\] The \(4\times 2\) latin rectangle on \([8]\), \[Q=\left[ \begin{array}{cc} 2 & 8 \\ 8 & 6 \\ 7 & 5 \\ 5 & 7 \end{array} \right]\] augments \(R\) of Example \[ex710\] to make a \(4\times 8\) latin rectangle \(R'\) on \([8]\). \[R'=\left[ \begin{array}{cccccccc} 1 & 5 & 4 & 3 & 7 & 6 & 2 & 8 \\ 2 & 1 & 5 & 4 & 3 & 7 & 8 & 6\\ 8 & 3 & 2 & 6 & 1 & 4 & 7 & 5 \\ 4 & 8 & 1 & 2 & 6 & 3 & 5 & 7 \end{array} \right]\] and thanks to Theorem \[thm450\] \(R'\) can be embedded in a latin square of order \(8\).
This time each column of \(Q\) is associated with a subset of edges of \(B^{\star}\).
\[def740\] If \(R\) is an \(r\times s\) latin rectangle on \(\Sigma\) then \(M(R,\Sigma,j)=\{\rho_i\sigma_k\,|\, (i,\sigma)\in [r]\times\Sigma \mbox{ and } R(i,j)=\sigma\}\).
\[ex750\] If \(Q\) is the \(4\times 2\) latin rectangle on \([8]\) in Example \[ex730\] then the edge-subsets \(M(Q,[8],1)\) and \(M(Q,[8],2)\) are the edge-sets of the graphs in Figure \[fig760\].
\(M(Q,[8],1)\) and \(M(Q,[8],2)\)
Rather than a inducing a 1-factorisation of \(B^{\star}\) the edge subsets \[M(Q,\Sigma,1), M(Q,\Sigma,2),\ldots ,M(Q,\Sigma,n-s)\] decompose \(E(B^{\star})\) into matchings of \(\cR\) into \(\cS\). A matching is little more than an independent set of edges.
\[def770\] If \(G\) is a graph then edges \(\{e,e'\}\subseteq E(G)\) are independent if and only if \(e\) and \(e'\) have no common end in \(G\). A set of edges \(E\subseteq E'\) is an independent set of edges if and only if every pair of edges \(\{e,e'\}\subseteq E\), \(e\neq e'\) are independent.
\[def790\] If \(G\) is a graph and \(A,B\subseteq V(G)\) then a set of edges \(E\subseteq E(G)\) is a matching of into if and only if \(E\) is an independent set of \(|A|\) edges \(ab\) with \(a\in A\), \(b\in B\).
\[lem820\] If an \(r\times s\) latin rectangle \(R\) on \(\Sigma\) can be embedded in an \(r\times n\) latin rectangle \(L\) on \(\Sigma\) and \(Q\) is the \(r\times (n-s)\) latin rectangle on \(\Sigma\) defined by \(Q(i,j)=L(i,s+j)\) for all \((i,j)\in [r]\times [n-s]\) then the set \[\{M(Q,\Sigma,1), M(Q,\Sigma,2),\ldots, M(Q,\Sigma,n-s)\}\] is a decomposition of \(E(B^{\star}(R,\Sigma))\) into matchings of \(\cR\) into \(\cS\).
Conversely, if \(\{M_i\,|\,i\in [n-s]\}\) is a decomposition of \(E(B^{\star})\) into matchings of \(\cR\) into \(\cS\) then the \(r\times n\) array \(L\) given by, \[L(i,j)=\left\lbrace \begin{array}{lcl} R(i,j) & \mbox{ if and only if } & (i,j)\in [r]\times [s] \\ \sigma_k & \mbox{ if and only if } & (i,j)\in [r]\times [n]\backslash [s]\mbox{ and } \rho_i\sigma_k\in M_{j-s} \end{array}\right.\] is an \(r\times n\) latin rectangle on \(\Sigma\) in which \(R\) is embedded.
Suppose \(R\) can be embedded in \(L\) and \(j\in [n-s]\). Let \(B^{\star}=B^{\star}(R,\Sigma)\) and \(M_j=M(Q,\Sigma,j)\). As \(M_j\subseteq E(B^{\star})\) it follows, if \(e\in E_j\), that \(e=\rho_i\sigma_k\) for some \(\rho_i\in\cR\) and \(\sigma_k\in\Sigma\). Therefore \(M_j\) is a matching of \(\cR\) into \(\cS\) if and only if \(M_j\) is an independent set of \(|\cR|=r\) edges.
As \((\cR,\Sigma\) is a bipartition of \(B^{\star}\) it follows that \(M_j\) is an independent set of \(r\) edges if and only if every vertex \(\rho_i\in\cR\) is incident with exactly one edge of \(M_j\) and every vertex \(\sigma_k\in\Sigma\) is incident with at most one edge of \(M_j\).
If $\rho_i\sigma_k\in M_j$ and $\rho_I\sigma_k\in E_j$ then, by
definition, $Q(i,j)=\sigma_k$ and $Q(I,j)=\sigma_k$. Therefore, as $Q$
has the latin property it follows that $i=I$. If $\rho_i\sigma_k\in M_j$
and $\rho_i\sigma_K\in M_j$ then, by definition, $Q(i,j)=\sigma_k$ and
$Q(i,j)=\sigma_K$ which implies that $k=K$. So every vertex of
$B^{\star}$ is the end of at most one edge of $M_j$. Now, because
$\rho_i\sigma_{k}\in M_j$ for $k=Q(i,j)$ and all $i\in [r]$, it follows
that every vertex $\rho_i\in\cR$ is the end of exactly one edge of $M_j$
and hence $M_j$ is a matching of $\cR$ into $\cS$.
To finish the proof of the first part of Lemma \[lem820\] it remains to
show that $\{M_1,\ldots, M_{n-s}\}$ is a decomposition of
$E(B^{\star})$. This follows if every edge of $E(B^{\star})$ is an edge
in exactly one $M_j$ for some $j\in [n-s]$.
If $\rho_i\sigma_k\in M_j$ and $\rho_i\sigma_k\in M_J$ then, by
definition, $Q(i,j)=\sigma_k$ and $Q(i,J)=\sigma_k$ and so, as $L$ has
the latin property, it follows that $j=J$. From the definition of
$B^{\star}$ it follows that $|E(B^{\star})|=r(n-s)$. Therefore, as
$|M_j|=r$ for all $j\in [n-s]$ it follows that
$\sum_{j\in [n-s]}|M_j|=r(n-s)$ and hence every edge of $E(B^{\star})$
is an edge in exactly one $M_j\in M$. Therefore $M$ is a decomposition
of $E(B^{\star})$ into matchings of $R$ into $S$.
Now suppose $M=\{M_i\,|\,i\in [n-s]\}$ is a decomposition of
$E(B^{\star})$ into matchings of $\cR$ into $\cS$. By definition $L$ is
an $r\times n$ array on $\Sigma$. $L$ is complete because $R$ is
complete and if $(i,j)\in [r]\times [n]\backslash [r]$ then for some
$\sigma_k\in\Sigma$ the matching $M_{j-s}$ contains an edge
$\rho_i\sigma_k$. Therefore, by definition, $L(i,j)=\sigma_k$. It
follows that $L$ is an $r\times n$ latin rectangle on $\Sigma$ if and
only if $L$ has the latin property.
If $(i,j)\in [r]^2$ and $(k,l)\in [s]^2$ then $L(i,j)=L(k,l)$ if and
only if $R(i,j)=R(k,l)$ which, as $R$ has the latin property, implies
that either $i=k$ and $j=l$ or $i\neq k$ and $j\neq l$.
If $(i,k)\in [r]^2$, $j\in [s]$, $l\in [n]\backslash [s]$ and
$L(i,j)=L(k,l)$ then $R(i,j)=L(k,l)$. Now, $L(k,l)=m$ if and only if
$\rho_k\sigma_m\in M_{l-s}$. Therefore, by the definition of
$B^{\star}$, it follows that $R(k,L)\neq m$ for all $L\in [s]$ and so,
in particular, $R(k,j)\neq m$. Therefore as $R(i,j)=m$ it follows that
$k\neq i$.
Finally, if $(i,k)\in [n]^2$, $(j,l)\in ([n]\backslash [s])^2$ and
$L(i,j)=L(k,l)=m$ then, by the definition of $L$ it follows that
$\rho_i\sigma_m\in M_j$ and $\rho_k\sigma_m\in M_l$. If $j=l$ then as
$M_j=M_l$ is a matching of $\cR$ into $\cS$ it follows that $i\neq k$.
Otherwise $j\neq l$, in which case, as $M$ is a decomposition of
$E(B^{\star})$ it follows that $i\neq k$.
Lemma \[lem820\], together with Theorem \[thm630\] and
Theorem \[thm450\], is sufficient to prove Theorem \[thm690\].
\[Ryser @HJR\] An $r\times s$ latin rectangle $R$ on $\Sigma$ can be
embedded in some latin square of order $n$ on $\Sigma$ if and only if
$R(\sigma)\geq r+s-n$ for all $\sigma\in\Sigma$.
The key to this proof is to recognise that, if
$B^{\star}=B^{\star}(R,\Sigma)$, then
$d(B^{\star},\sigma_k)=r-R(\sigma_k)$ for all $\sigma_k\in\Sigma$. This
fact comes from the observation that $\sigma_k$ is joined, in
$B^{\star}$, to every vertex $\rho_i\in\cR$ except those $R(\sigma_k)$
vertices $\rho_i$ which correspond to the $R(\sigma_k)$ rows of $R$
which contain symbol $\sigma_k$.
If $R$ can be embedded in a latin square of order $n$ on $\Sigma$ then,
trivially, $R$ can be embedded in an $r\times n$ latin rectangle on
$\Sigma$. By Lemma \[lem820\] if $R$ can be embedded in an $r\times n$
latin rectangle on $\Sigma$ then $E(B^{\star})$ has a decomposition into
$n-s$ matchings of $\cR$ into $\Sigma$. However, if $R(\sigma_k)<r+s-n$
for some $\sigma_k\in\Sigma'$ then, as
$d(B^{\star},\sigma_k)=r-R(\sigma_k)> r-(r+s-n)=n-s$ it follows that
$E(B^{\star})$ does not have a decomposition into $n-s$ matchings of
$\cR$ into $\Sigma$. Therefore is $R$ is completable it follows that
$R(\sigma_k)\geq r+s-n$ for all $\sigma_k\in\Sigma$.
Conversely, if $R(\sigma_k)\geq r+s-n$ for all $\sigma_k\in\Sigma$ then
$d(B^{\star},\sigma_k)\leq n-s$ for all $\sigma_k\in\Sigma$. Therefore,
as $d(B^{\star},\rho_i)=n-s$ for all $\rho_i\in\cR$ and $(R,\Sigma)$ is
a bipartition of $B^{\star}$ it follows from Theorem \[thm630\] that
$B^{\star}$ is $(n-s)$-edge-colourable.
Let $\phi:E(B^{\star})\rightarrow\{c_i\,|\,i\in [n-s]\}$ be an
$(n-s)$-edge-colouring, let $\cB=(B,\phi)$ be the corresponding
$(n-s)$-edge-coloured graph and let $M_j=[\cB,c_j]$ be the colour-class
of $c_j$ in $\cB$ for all $j\in [n-s]$.
If $j\in [n-s]$ then, because $\phi$ is proper, it follows that $M_j$ is
an independent set of edges. As $d(B^{\star},\rho_i)=n-s$ every vertex
$\rho_i\in\cR$ is an end of some edge of every colour
$c_1,\ldots ,c_{n-s}$. Therefore, $|M_j|=r$ for all $j\in [n-s]$. Now,
because $e\in M_j$ implies $e=\rho_i\sigma_k$ for some $\rho_i\in\cR$
and $\sigma_k\in\Sigma$ it follows that $M_j$ is a matching of $\cR$
into $\Sigma$.
If $\rho_i\sigma_k\in M_j$ and $\rho_i\sigma_k\in M_J$ then
$\phi(\rho_i\sigma_k)=j$ and $\phi(\rho_i\sigma_k)=J$. Consequently,
$j=J$. Therefore, as every edge is coloured in $\cB$, it follows that
$\{M_i\,|\,i\in [n-s]\}$ is a decomposition of $B^{\star}$ into
matchings of $\cR$ into $\cS$. Therefore, by Lemma \[lem820\], $R$ can
be embedded in a $r\times n$ latin rectangle on $\Sigma$ and so, by
Theorem \[thm450\], $R$ can be embedded in some latin square of order
$n$ on $\Sigma$.
Theorem \[thm690\] is a generalisation of Theorem \[thm450\] because if
$s=n$ then Theorem \[thm690\] says that $R$ can be embedded in a latin
square of order $n$ on $\Sigma$ if and only if $R(\sigma)\geq r$ for all
$\sigma\in\Sigma$, which is a trivial condition as $R(\sigma)=r$ for all
$\sigma\in\Sigma$ in an $r\times n$ latin rectangle $R$ on $\Sigma$.
Theorem \[thm690\] also answers the original question about whether, for
an $r\times s$ latin rectangle $R$, there is a finite $N=N(r,s)$ such
that $R$ can be embedded in some latin square of order $N$.
Theorem \[thm690\] says that $R$ can be embedded in some latin square of
order $N=r+s-min_{\sigma\in\Sigma'}R(\sigma)$ on $\Sigma$In Evans (1960) Evans applied Theorem \[thm690\] to prove that a partial latin square of order \(n\) can be embedded in a latin square of order \(t\) for all \(t\geq 2n\).
\[Evans @TEV\] \[thm830\] A partial latin square of order \(n\) can be embedded in some \(t\times t\) latin square for all \(t\geq 2n\)
The proof presented is for natural latin squares. The extension to latin squares in general is trivial.
Suppose \(t\geq 2n\). Let \(A\) be a natural partial latin square of order \(n\) and \(B\) a natural latin square of order \(t-n\). Now let \(C\) be the \(n\times n\) array of order \(t\) given by \[C(i,j)=\left\lbrace \begin{array}{lll} A(i,j) & \mbox{ if and only if } & A(i,j)\mbox{ filled }\\ B(i,j)+n & \mbox{ if and only if } & A(i,j)\mbox{ empty } \end{array}\right.\] Then \(C\) is an \(n\times n\) latin rectangle on \(S\subseteq [t]\) in which \(A\) is embedded. As \(t\geq 2n\) it follows that \(2n-t\leq 0\) and so Theorem \[thm690\] implies that \(C\) can be embedded in some natural latin square \(L\) of order \(t\). \(L\) is a natural latin square of order \(t\) in which \(A\) is embedded.
Figure \[fig840\] gives an example of Evans’ construction for embedding a natural partial latin square of order \(4\) in a natural latin square of order \(8\).
| $A= | $B= | $C= |
| \left[ \begin{array}{cccc} | \left[ \begin{array}{cccc} | \left[ \begin{array}{cccc} |
| 1 & 4 & 2 & - \ 1 & 2 & 3 & 4 \ 1 & 4 & 2 & 8 \ | ||
| - & 2 & - & - \ 2 & 3 & 4 & 1 \ 6 & 2 & 8 & 5\ | ||
| - & 1 & 3 & - \ 3 & 4 & 1 & 2 \ 7 & 1 & 3 & 6\ | ||
| - & 3 & - & 4 4 & 1 & 2 & 3 8 & 3 & 6 & 4 | ||
| \end{array}] \end{array}] \end{array}] | ||
| $ | $ | $ |
Evans also gave a remarkable construction, for all \(n\geq 4\), of a natural partial latin square of order \(n\) which cannot be embedded in a latin square of order \(t\) for all \(t<2n\). Thereby proving that the bound in Theorem \[thm830\] is best possible in general. This construction is reproduced in Definition \[def850\]. Figure \[fig860\] illustrates the construction in Definition \[def850\] and Figure \[fig870\] gives an example of a natural partial latin square of order \(4\) which cannot be embedded in a latin square of order \(t\) for all \(t<8\).
\[def850\] For \(n\geq 4\) let \(X_n\) be the array of order \(n\) given by \[X_n(i,j)=\left\lbrace \begin{array}{ccl} (i+j-1)_n & if & (i,j)\in [n-2]\times [n] \mbox{ or }\\ & & i=n-1\mbox{ and } j\in\{1,4,5,\ldots ,n\} \mbox{ or }\\ & & i=n, j\in\{1,3,4,\ldots , n\}\\ 1 & if & i=n-1, j=2 \end{array}\right.\] where \[(k)_n=\left\lbrace \begin{array}{cc} k\bmod n & \mbox{ if } n\nmid k \\ n & \mbox{ if } n\mid k \end{array}\right.\]
\[\begin{array}{|c|c|c|c|c|c|} \hline 1 & 2 & 3 & \cdots & n-1 & n\\ \hline 2 & 3 & 4 & \cdots & n & 1 \\ \hline & & & & & \\ \vdots & \vdots & \vdots & & \vdots & \vdots \\ & & & & & \\ \hline n-1 & 1 & - & \cdots & n-3 & n-2 \\ \hline n & - & 2 & \cdots & n-2 & n-1 \\ \hline \end{array}\] \[fig860\]
\[\left[\begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 3 & 4 & 1 \\ 3 & 1 & - & 2 \\ 4 & - & 2 & 3 \end{array}\right]\]
\[lem880\] For all \(n\geq 4\), the array \(X_n\) is a natural partial latin square of order \(n\) which cannot be embedded in a latin square of order \(t\) for all \(t\in [2n-1]\backslash [n-1]\)
First it is shown that \(X_n\) is a natural partial latin square. By definition \(X_n\) is an \(n\times n\) array on \([n]\). It suffices, therefore, to check that \(X_n\) has the latin property.
If \((k,l)\in [n]^2\) and \((i,j)\in [n]^2\backslash\{(n,2),(n-1,2),(n-1,3)\}\) then by definition \(X_n(i,j)=(i+j-1)_n\) and \(X_n(k,l)=(k+l-1)_n\). Therefore \(X_n(i,j)=X_n(k,l)\) if and only if \((i+j-1)_n=(k+l-1)_n\). If \(n\nmid (i+j-1)\) and \(n\nmid (k+l-1)\) then, by definition, \((i+j-1)_n=(i+j-1)\bmod{n}\) and \((k+l-1)_n=(k+l-1)\bmod{n}\). Therefore, if \(i=k\), as \(\{j,l\}\in [n]\), it follows that \(j=l\) and if \(i\neq k\) then \(j\neq l\).
If \(n\) divides exactly one of \(i+j-1\), \(k+l-1\) then without loss of generality assume that \(n\mid (i+j-1)\) and \(n\nmid (k+l-1)\). Then, by definition, \((i+j-1)_n=n\) and \((k+l-1)_n=k+l-1\bmod{n}\). Therefore \((i+j-1)_n\neq (k+l-1)_n\). Otherwise \(n\mid (i+j-1)\) and \(n\mid (k+l-1)\) in which case, as \((i,j)\in [n]^2\) it follows that \(i+j-1=k+l-1=n\). Therefore, if \(i=k\), it follows that \(j=l\) and, if \(i\neq k,\) then \(j\neq l\).
If \((i,j)\in\{(n,2),(n-1,2),(n-1,3)\}\) is a filled cell of \(X_n\) then \((i,j)=(n-1,2)\) and \(X_n(i,j)=1\). Suppose \(X_n(k,l)=1\). Then, as \(n>1\), either \((k,l)=(n-1,2)\) or \((k+l-1)_n=(k+l-1)\bmod{n}=1\). If \((k+l-1)\bmod{n}=1\) then \(k+l\equiv 2\bmod{n}\) and so, if \(k=i=n-1\), it follows that \(l=3\). This is a contradiction as \(X_n(n-1,3)\) is empty. If \(l=j=2\) then \(k=n\) which is another contradiction as \(X_n(n,2)\) is empty. Therefore \(X_n\) has the latin property.
Now let \(n\geq 4\) and suppose that \(X_n\) can be embedded in a latin square \(L\) of order \(t\), where \(t\in [2n-1]\backslash [n]\). Let \(R\) be the \(n\times n\) latin rectangle on \([n]\cup\{a,b\}\) defined by \(R(i,j)=L(i,j)\) for all \(i,j\in [n]\), \(R(n,2)=a\) and \(R(n-1,3)=b\).
As \(R\) can be embedded in a latin square of order \(t\) it follows from Theorem \[thm690\] that \(R(k)\geq 2n-t\) for all \(k\in [t]\). As \(t<2n\) it follows that \(R(k)>0\) for all \(k\in [t]\).
If \(t\geq n+3\) then, as \(|([t]\backslash [n])\backslash\{a,b\}|\geq t-n-2\geq 1\) it follows that \(\exists c\in([t]\backslash [n])\backslash\{a,b\}\). As \(R\) is a latin rectangle on \([n]\cup\{a,b\}\) it follows that \(R(c)=0\). This is a contradiction and therefore \(X_n\) cannot be embedded in a latin square of order \(t\), for all \(t\in [2n-1]\backslash [n+2]\).
If \(t=n+2\) then \(R(k)\geq 2n-t=n-2\geq 2\) for all \(k\in [n]\). This is a contradiction because \(R(i,j)\in\{n+1,n+2\}\) only if \((i,j)=(n,2)\) or \((i,j)=(n-1,3)\) and so \(R(k)\leq 1\) for at least one \(k\in\{n+1,n+2\}\). If \(t=n+1\) then \(R(k)\geq 2n-t=n-1=3\), which is a contradiction because \(R(n+1)\leq 2\). If \(t=n\) then \(R(k)\geq n\) for all \(k\in [n]\) is contradicted because \(R(1)\leq n-1\).
In this section it was shown how to apply graph theory to the problem of embedding latin rectangles. This is the essential method of the later chapters of this thesis. The remaining sections of this introduction are more concerned with showing how the problems which are solved in those later chapters have arisen. The next section is about analogues of Theorem \[thm690\] and Theorem \[thm830\] for symmetric latin squares.
2.2 Embedding Symmetric Latin Rectangles {#sec885}
Theorem \[thm690\] implies that a symmetric \(r\times r\) latin rectangle \(R\) can be embedded in some latin square of order \(n\) on \(\Sigma\) if and only if \(R(\sigma)\geq 2r-n\) for all \(\sigma\in\Sigma\). However, Theorem \[thm690\] does not say that the embedded latin square itself will be symmetric. In fact, by Lemma \[lem320\], this symmetric embedding is possible only if \(R\) can be embedded in an admissible symmetric partial latin square of order \(n\). There are certainly cases in which this cannot be accomplished.
\[ex890\] If \(n=7\) then the \(4\times 4\) latin rectangle \(R\) in Figure \[fig900\] satisfies \(R(k)\geq 2r-n=1\) for all \(k\in [7]\) and yet cannot be embedded in a latin square of order \(2r-1=7\) because the symmetric partial latin square \(P\) of order \(7\) in Figure \[fig910\] is not admissible. In fact \(|O(P)|=|\{1,4,5,6,7\}|=5>n-d(P)=7-4=3\)
\[R= \left[ \begin{array}{cccc} 1 & 2 & 3 & 4 \\ 2 & 1 & 5 & 6 \\ 3 & 5 & 2 & 7 \\ 4 & 6 & 7 & 3 \end{array} \right]\]
\[P=\left[ \begin{array}{ccccccc} 1 & 2 & 3 & 4 & - & - & - \\ 2 & 1 & 5 & 6 & - & - & - \\ 3 & 5 & 2 & 7 & - & - & - \\ 4 & 6 & 7 & 3 & - & - & - \\ - & - & - & - & - & - & - \\ - & - & - & - & - & - & - \\ - & - & - & - & - & - & - \end{array}\right]\]
If \(R\) is an \(r\times r\) latin rectangle which can be embedded in a latin square of order \(n\) on \(\Sigma\) then the \(n\times n\) partial latin square \(P\), of order \(n\) on \(\Sigma\), defined by \(P(i,j)=R(i,j)\) for all \(\{i,j\}\subseteq [r]\) and otherwise \(P(i,j)\) empty is completable and therefore, by Lemma \[lem320\], admissible.
If \(n\) is odd this observation implies that \(d(P,\sigma)\leq 1\) for all \(\sigma\in\Sigma\). It follows that the \(r\) filled cells on the main diagonal of \(P\) contain \(r\) distinct symbols. As \(P\) is symmetric every remaining symbol in \(\Sigma\) is contained in an even number of cells of \(P\) and hence exactly \(r\) symbols \(\sigma\in\Sigma\) occur in an odd number of cells of \(P\). Therefore \(R(\sigma)\) is odd for exactly \(r\) symbols \(\sigma\in\Sigma\).
If \(n\) is even then, as the main diagonal of \(P\) is admissible, it follows that \(|O(P)|\leq n-d(A)=n-r\). This says that at most \(n-r\) symbols \(\sigma\) are contained in an odd number of cells on the main diagonal of \(P\). Every remaining symbol is contained in an even number of cells of \(P\) and hence, therefore, of \(R\). So \(R(\sigma)\) is even for at least \(r\) symbols \(\sigma\in\Sigma\).
In general an \(r\times r\) latin rectangle \(R\) on \(\Sigma\) can be embedded in a latin square of order \(n\) on \(\Sigma\) only if \(R(\sigma)\equiv n\bmod{2}\) for at least \(r\) different symbols \(\sigma\). Remarkably it was proved by Cruse Cruse (1974) that along with \(R(\sigma)\geq 2r-n\) this condition is sufficient for an embedding.
\[Cruse @ABC\] \[thm920\] An \(r\times r\) symmetric latin rectangle \(R\) on \(\Sigma\) can be embedded in some symmetric latin square of order \(n\) on \(\Sigma\) if and only if \(R(\sigma)\geq 2r-n\) for all \(\sigma\in\Sigma\) and \(R(\sigma)\equiv n\bmod{2}\) for at least \(r\) symbols \(\sigma\in\Sigma\).
Like Theorem \[thm690\] this result has, as a corollary, the best possible bound for embedding a symmetric latin rectangle in a symmetric latin square. However, because a symmetric latin square of order \(n\) necessarily has \(n\) distinct symbols on the main diagonal, this embedding is only possible, in general, if \(n\) is even. If \(n\) is odd then it is also necessary that \(R\) have \(r\) distinct symbols on its main diagonal.
\[Cruse @ABC\] \[thm925\] If \(t\geq 2r\) is even then an \(r\times r\) symmetric latin rectangle on \(\Sigma\) can be embedded in some symmetric latin square of order \(t\) on \(\Sigma\). If \(t>2r\) is odd then an \(r\times r\) symmetric latin rectangle on \(\Sigma\) can be embedded in some symmetric latin square of order \(t\) if and only if the main diagonal of \(R\) contains \(r\) distinct symbols.
There is a very close correspondence between symmetric latin squares and edge-coloured complete graphs. It turns out that the problem of embedding a symmetric latin rectangle in a latin square is precisely the same as the problem of embedding an \(n\)-edge-coloured complete graph of order \(r\) in an \(n\)-edge-coloured complete graph of order \(n\).
\[def930\] The complete graph of order is the graph with vertex set \(V(\Knl)=\{v_i\,|\, i\in [n]\}\) and edge-set \(E(\Knl)=\{v_iv_j\,|\,v_i\in V,v_j\in V\}\)
It is well known that the chromatic index of the complete graph of order \(n\) is \(n\).
\[def940\] \(\chi'(\Knl)=n\)
There is an obvious correspondance between \(n\)-edge-coloured complete graphs and symmetric latin squares of order \(n\). This correspondance can, equally obviously, be extended to a more general correspondance between symmetric arrays and edge-coloured graphs.
\[def952\] If \(\cG\) is a \(\Sigma\)-edge-coloured graph of order \(r\) then \(A=A(\cG)\) is the symmetric array on corresponding to if and only if \(A(i,j)=\phi(v_iv_j)\) for all \(\{i,j\}\subseteq [r]\) such that \(v_iv_j\in E(G)\). Conversely if \(A\) is a symmetric \(r\times r\) array on \(\Sigma\) then \(\cG=\cG(A)\) is the \(\Sigma\)-edge-coloured graph of order corresponding to if and only if \(E(G)=\{v_iv_j\,|\, A(i,j)\mbox{ is filled}\}\) and \(\phi(v_iv_j)=A(i,j)\) for all \(v_iv_j\in E(G)\).
The most general latin structure considered in this thesis is the partial latin rectangle of Definition \[def9525\].
\[def9525\] An partial latin rectangle on \(\Sigma\) is an \(r\times s\) array on \(\Sigma\) with the latin property.
A symmetric partial latin rectangle corresponds exactly with a proper edge-coloured complete graph.
\[lem953\] \(\cG\) is a proper \(\Sigma\)-edge-coloured graph of order \(r\) if and only if \(A(\cG)\) is an \(r\times r\) symmetric partial latin rectangle on \(\Sigma\).
If \(\cG\) is a \(\Sigma\)-edge-coloured graph of order \(n\) then, by definition, \(A(\cG)\) is a symmetric \(r\times r\) array on \(\Sigma\). Therefore \(A=A(\cG)\) is an \(r\times r\) symmetric partial latin rectangle on \(\Sigma\) if \(A\) has the latin property. Let \((i,j)\) and \((k,l)\) be filled cells of \(A\) such that \(A(i,j)=A(k,l)=m\). Then, by definition, \(\phi(v_iv_j)=\phi(v_kv_l)=m\). Therefore, if \(i=k\), as \(\phi\) is proper, it follows that \(j=l\). Consequently, \(A\) has the latin property.
Conversely, if \(A\) is an \(r\times r\) symmetric partial latin rectangle on \(\Sigma\) then, by definition, \(\cG(A)\) is \(\Sigma\)-edge-coloured graph of order \(r\). It suffices, therefore, to show that \(\cG(A)\) is proper. If \(\phi(v_iv_j)=\phi(v_iv_l)\) then, as \(A\) has the latin property, it follows that \(j=l\). Therefore \(\cG\) is proper.
Now, a partial latin square of order \(n\) on \(\Sigma\) is an \(n\times n\) partial latin rectangle on \(\Sigma\), an \(r\times s\) latin rectangle on \(\Sigma\) is a complete \(r\times s\) partial latin rectangle on \(\Sigma\) and a latin square of order \(n\) on \(\Sigma\) is an \(n\times n\) latin rectangle of order \(n\) on \(\Sigma\). Therefore Corollary \[cor954\] follows from Lemma \[lem953\].
\[cor954\] \(\cG\) is a proper \(\Sigma\)-edge-coloured graph of order \(n\) if and only if \(A(\cG)\) is a symmetric partial latin square of order \(n\) on \(\Sigma\). \(\cG\) is a proper \(\Sigma\)-edge-coloured complete graph of order \(r\) if and only if \(A(\cG)\) is a symmetric \(r\times r\) latin rectangle on \(\Sigma\) and \(\cG\) is a proper \(\Sigma\)-edge-coloured complete graph of order \(n\) if and only if \(A(\cG)\) is a symmetric latin square of order \(n\) on \(\Sigma\).
\[ex955\] The 5-edge-coloured complete graph \(\cG(L)\) of order 5 shown in Figure \[fig960\] corresponds to the latin square \(L\) of order 5 under the correspondance given by the key of Figure \[fig960\]. \[L=\left[ \begin{array}{ccccc} 1 & 2 & 3 & 4 & 5 \\ 2 & 3 & 4 & 5 & 1 \\ 3 & 4 & 5 & 1 & 2 \\ 4 & 5 & 1 & 2 & 3 \\ 5 & 1 & 2 & 3 & 4 \\ \end{array} \right]\]
A 5-edge-coloured \(K_5^l\)
The ideas of completing partial latin squares and embedding latin rectangles have their obvious parallels in the world of edge-coloured complete graphs.
\[def970\] An edge-coloured graph \(\cG\) is embedded in an edge-coloured graph \(\cK\) if and only if \(G\triangleleft K\) and \(\phi(e)=\psi(e)\) for all \(e\in E(K)\cap E(G)\).
\[ex980\] The 5-edge-coloured graph of Figure \[fig990\] is embedded in the 5-edge-coloured graph of Figure \[fig960\].
A 5-edge-coloured graph
With a little more notation, Theorem \[thm920\] is easily translated into a problem about embedding edge-coloured complete graphs.
\[def1020\] If \(\cG\) is a \(\Sigma\)-edge-coloured graph then, for all \(\sigma\in\Sigma\) \[E(\sigma)=\{e\in E(G)\,|\,e\mbox{ is not a loop and } \phi(e)=\sigma\}\] \[L(\sigma)=\{e\in E(G)\,|\,e\mbox{ is a loop and }\phi(e)=\sigma\}\] \(e(\sigma)=|E(\sigma)|\) and \(l(\sigma)=|L(\sigma)|\).
\[def1030\] If \(\cG\) is a \(\Sigma\)-edge-coloured graph then, \[O(\cG)=\{\sigma\in\Sigma\,|\, l(\sigma)\equiv (n+1)\bmod{2}\}\] and \(o(\cG)=|O(\cG)|\).
\[def1040\] A proper \(\Sigma\)-edge-coloured complete graph of order \(r\) is -Ryser if and only if \(2e(\sigma)+l(\sigma)\geq 2r-n\) for all \(\sigma\in\Sigma\).
\[def1050\] A proper edge-coloured complete graph \(\cG\) is -admissible if and only if \(n\) is odd and \(l(\sigma)\leq 1\) for all \(\sigma\in\Sigma\) or \(n\) is even and \(o(\cG)\leq n-r\).
Theorem \[thm1060\] is the precise graph theory analogue of Theorem \[thm920\].
\[thm1060\] A proper \(\Sigma\)-edge-coloured complete graph \(\cG\) of order \(r\) can be embedded in a proper \(\Sigma\)-edge-coloured complete graph of order \(n\) if and only if \(\cG\) is \(n\)-Ryser and \(n\)-admissible.
Rather than prove Theorem \[thm1060\] directly it is shown, in Section \[sec1330\], how Theorem \[thm1060\] follows from a more general result Theorem \[thm1630\] due, independently, to Andersen Lars Døvling Andersen (1982) and to Hoffman Hoffman (1983), about embedding symmetric latin rectangles with a prescribed main diagonal. Prior to that, in Section \[sec1250\], the topic of prescribed main diagonal embeddings is introduced. This topic is a legacy of the work discussed in the next section about embedding idempotent latin rectangles.
2.3 Idempotent Latin Rectangles
The algebraic background to the problem of embedding latin rectangles has lead some to consider idempotent latin squares and the corresponding problem of idempotent embeddings of latin rectangles. Recall that an idempotent of a ring is an element \(a\) such that \(a^2=a\). Therefore if \(M\) is the multiplication table of the multiplicative group of a ring in which \(a\) is an idempotent it follows that \(M(a,a)=a\).
In this section, as is common in the literatue, it is presumed that an idempotent latin square is natural.
\[def1070\] An \(r\times s\) array \(A\) on \([n]\) is idempotent if and only if \(A(i,i)=i\) for all \(i\in [min(r,s)]\).
It would be nice to have an analogue of Theorem \[thm690\] for embedding an idempotent latin rectangle in an idempotent latin square. Unfortunately there is, at the time of writing, no such result. There is a Ryser-type necessary condition but it is known that this condition alone is insufficient. One of the main aims of this section is to introduce the work of Andersen on characterising for \(n\) those idempotent latin rectangles which satisfy this condition and yet cannot be embedded in an idempotent latin square of order \(n\).
In general, if \(r\neq s\) then an \(r\times s\) idempotent latin rectangle \(R\) cannot be embedded in an idempotent latin square. For example, if \(r<s\) and \(R\) is embedded in an idempotent latin square \(L\) of order \(n\) then as \(L(r+1,r+1)=r+1\) it follows that \(R(i,r+1)\) for all \(i\in [r]\) . Therefore every \(r\times s\) (\(r<s\)) idempotent latin rectangle with symbol \(r+1\) in column \(r+1\) cannot be embedded in an idempotent latin square.
\[ex1075\] The presence of symbol 4 in the fourth column of this \(3\times 4\) idempotent latin rectangle prevents it from being embedded in an idempotent latin square of order \(n\) for all \(n\geq 6\). \[\left[\begin{array}{cccc} 1 & 3 & 4 & 5 \\ 3 & 2 & 1 & 4 \\ 5 & 6 & 3 & 1 \\ \end{array}\right]\]
More importantly it can be shown that an \(r\times s\) latin rectangle can be embedded in a latin square of order \(n\) if and only if there is either an \(r\times r\) or \(s\times s\) latin rectangle which can be embedded in a latin square of order \(n\). For these reasons it makes sense to consider \(r\times r\) idempotent latin rectangles. In this case it is easy to obtain a necessary condition similar to the condition of Theorem \[thm690\]. This condition is proved to be necessary in Lemma \[lem1077\]. The proof Lemma \[lem1077\], and others beside, involves the notation given in Definition \[def1076\].
\[def1076\] If \(L\) is a latin square of order \(n\) on \(\Sigma\) and \(r\in [n]\) then\[L(R,\sigma)=\{(i,j)\,|\, (i,j)\in [r]^2\mbox{ and } L(i,j)=\sigma\}\]\[L(A,\sigma)=\{(i,j)\,|\, (i,j)\in [r]\times [n-r]\backslash [r]\mbox{ and } L(i,j)=\sigma\}\]\[L(B,k)=\{(i,j)\,|\,(i,j)\in [n]\backslash [r]\times [n]\mbox{ and }L(i,j)=\sigma\}\]
\[10765\] An idempotent \(r\times r\) latin rectangle \(R\) is -Ryser if and only if \(R(k)\geq 2r-n\) for all \(k\in [r]\) and \(R(k)\geq 2r-n+1\) for all \(k\in [n]\backslash [r]\).
\[lem1077\] An \(r\times r\) idempotent latin rectangle \(R\) can be embedded in an idempotent latin square of order \(n\) only if \(R\) is \(n\)-Ryser.
Suppose \(R\) is an \(r\times r\) idempotent latin rectangle and \(L\) is an idempotent latin square of order \(n\) in which \(R\) is embedded.
If \(k\in [r]\) then \(|L(A,k)|\leq n-r\) and \(|L(B,k)|=n-r\). Therefore, as \(|L(R,k)|+|L(A,k)|+|L(B,k)|=n\) it follows that \(R(k)\geq n-2(n-r)\) and therefore \(R(k)\geq 2r-n\). If \(k\in [n]\backslash [r]\) then \(|L(A,k)|\leq n-r-1\) because \(L(j,j)=k\) for some \(j\in [n]\backslash [r]\), Again \(L(B,k)=n-r\) so this time \(R(k)\geq 2r-n+1\).
Unfortunately being \(n\)-Ryser alone is not sufficient for an \(r\times r\) idempotent latin rectangle to be embeddable in some latin square of order \(n\). Example \[ex1078\] is originally from Lindner and Evans (1977) and gives an example of a \(3\times 3\) idempotent latin rectangle which cannot be embedded in an idempotent latin square of order \(5\) despite being \(5\)-Ryser.
\[ex1078\] The \(3\times 3\) idempotent latin rectangle \(R\) of order \(5\) in Figure \[fig1079\] is \(5\)-Ryser because \(2r-n=1\) and each symbol of \(\{1,2,3\}\) is contained in at least one cell and each symbol of \(\{4,5\}\) is contained in at least two cells. Nevertheless \(R\) cannot be embedded in an idempotent latin square of order \(5\). If \(R\) could be embedded in an idempotent latin square \(L\) of order \(5\) then some cell in the fourth column of \(L\) would contain symbol \(5\). However, symbol \(5\) cannot be contained in a cell of any of the first three rows because each of the three rows of \(R\) contains symbol \(5\), cannot be contained in cell \((4,4)\) because \(L(4,4)=4\) and cannot be contained in cell \((4,5)\) because \(L(5,5)=5\). Therefore no cell of the fourth column of \(L\) can contain symbol \(5\), contradicting \(L\) being a latin square. Therefore the assumption that \(R\) can be embedded in an idempotent latin square of order \(5\) is untenable.
\[\left[ \begin{array}{ccc} 1 & 5 & 4 \\ 4 & 2 & 5 \\ 5 & 4 & 3 \end{array}\right]\]
In his thesis Andersen made significant progress towards resolving the difficulities of this problem and attempted to give a characterisation of \(n\)-Ryser idempotent \(r\times r\) latin rectangles of order \(n\) which cannot be embedded in a latin square of order \(n\). This classification is based upon obtaining necessary and sufficient conditions for an \(n\)-Ryser idempotent \(r\times r\) latin square of order \(n\) to be embedded in an \(n\)-Ryser idempotent \((r+1)\times (r+1)\) latin square of order \(n\). This approach is a recurring theme of later work in this line, chiefly done by Allen, Andersen, Hilton and Rodger, and is also taken up in both remaining chapters of this thesis.
\[def1080\] An -Ryser -extension of an idempotent \(r\times r\) latin square \(R\) of order \(n\) is an \(n\)-Ryser \((r+1)\times (r+1)\) natural latin square \(Q\) of order \(n\) in which \(R\) is embedded and for which \(Q(r+1,r+1)=m\). If \(R\) has an \(n\)-Ryser \(m\)-extension then \(R\) is said to be Ryser -extendible.
If an idempotent latin rectangle \(R\) can be embedded in a latin square then \(R\) must be fully extendible, which is to say that \(R\) is Ryser \(m\)-extendible for every \(m\in [n]\backslash [r]\). This is the first instance of a general phenomena which occurs in both of the remaining chapters of this thesis.
\[def1087\] An idempotent \(r\times r\) latin rectangle \(R\) is fully extendible if and only if \(R\) is \(n\)-Ryser \(m\)-extendible for every \(m\in [n]\backslash [r]\).
\[lem1085\] If an idempotent \(r\times r\) latin rectangle \(R\) can be embedded in an idempotent latin square of order \(n\) then \(R\) is fully extendible.
Suppose \(R\) can be embedded in an idempotent latin square \(L\) of order \(n\). As \(R\) is idempotent it follows that \(L(m,m)=m\). Let \(R'\) be the \((r+1)\times (r+1)\) latin rectangle defined by \(R'(i,j)=R(i,j)\) for all \((i,j)\in [r]^2\), \(R'(i,r+1)=L(i,m)\), \(R'(r+1,i)=L(m,i)\) for all \(i\in [r]\) and \(R'(r+1,r+1)=m\). Then \(R'\) is an \((r+1)\times (r+1)\) latin rectangle in which \(R\) is embedded. Moreover, \(R'\) can be embedded in a latin square of order \(n\), so by Lemma \[lem1077\] \(R'\) is Ryser. As \(R'(r+1,r+1)=m\) it follows that \(R'\) is a Ryser \(m\)-extension of \(R\).
In general, if \(R\) is an \(r\times s\) array with the latin property which satisfies a condition like that of being \(n\)-Ryser, in other words \(R(k)\geq f(n,r,s,\ldots)\) for some \(f\), and, moreover, \(R\) can be extended to an \((r+1)\times (s+1)\) array which satisfies an extended version of the same condition, i.e. \(R(k)\geq f(n,r+1,s+1,\ldots)\) then there are certain symbols, those symbols which only just satisfy the original condition, which only satisfy the latter condition because they are contained in either a cell of the \((r+1)\)st row or \((r+1)\)st column. In other words an alternative extension in which the same symbol did not appear in the \((r+1)\)st row or \((r+1)\)st column would fail to satisfy the desired condition.
\[def1090\] If \(R\) is an \(n\)-Ryser idempotent \(r\times r\) latin rectangle then a symbol \(k\in [n]\) is -critical for \(R\) if and only if \(k\in [r]\) and \(R(k)=2r-n\) or \(k\in [n]\backslash [r]\) and \(R(k)=2r-n+1\) and -semi-critical for \(R\) if and only if \(k\in [r]\) and \(R(k)=2r-n+1\) or \(k\in [n]\backslash [r]\) and \(R(k)=2r-n+2\).
Although it is not proved here directly one can show that, if \(R\) is an idempotent \(r\times r\) latin rectangle, then an idempotent \((r+1)\times (r+1)\) latin rectangle in which \(R\) is embedded is \(n\)-Ryser if and only if every critical symbol occurs in both the \((r+1)\)st row and \((r+1)\)st column and every semi-critical symbol occurs either in the \((r+1)\)st row or \((r+1)\)st column. Observe that symbol \(r+1\) which appears at the intersection of the \((r+1)\)st row and \((r+1)\)st column automatically satisfies this requirement.
\[ex1100\] Figure \[fig1110\] shows, on the left, an \(8\)-Ryser \(6\)-extension of an idempotent \(5\times 5\) latin rectangle \(R\) while on the right \(R\) is embedded in an idempotent \(6\times 6\) latin rectangle which is not \(8\)-Ryser. The difference is due to symbol 7 which is \(8\)-critical for \(R\) and, while on the left appears in a cell of both the sixth column and a cell of the sixth row, on the right is contained in no cell of the sixth column.
| $\left[ | $\left[ |
| \begin{array}{cccccc} | \begin{array}{cccccc} |
| & 3 & 4 & 8 & & 2 \ | & 3 & 4 & 8 & & 2 \ |
| & 2 & 1 & 3 & & 7 \ | & 2 & 1 & 3 & & 5 \ |
| & 6 & 3 & 1 & & 4 \ | & 6 & 3 & 1 & & 4 \ |
| & 5 & 2 & 4 & & 8 \ | & 5 & 2 & 4 & & 8 \ |
| & 7 & 8 & 2 & & 1 \ | & 7 & 8 & 2 & & 1 \ |
| 2 & 8 & 5 & 7 & 3 & 6 | 2 & 8 & 5 & 7 & 3 & 6 |
| \end{array}] | \end{array}] |
| $ | $ |
Andersen was successful in proving that, essentially, there are only two types of Ryser idempotent latin rectangles which are not fully-extendible. These types can be described purely in terms of the existence of certain symbol sets which satisfy certain conditions. This description probably makes sense for defining these types, but the impossibility of embedding is best appreciated by introducing associated bipartite graphs, in a manner similar to earlier results, and showing how certain connected components of these graphs prevent the existence of the necessary matchings required for an extension.
\[def1120\] If \(R\) is an \(r\times s\) latin rectangle on \(\Sigma\) then \[N(\rho,\sigma)=\{i\in [n]\,|\,R(i,j)\neq \sigma\mbox{ for all } j\in [s]\}\] \[N(c,\sigma)=\{j\in [n]\,|\, R(i,j)\neq \sigma\mbox{ for all } i\in [r]\}\] If \(S\subseteq\Sigma\) then \(N(\rho,S)=\cup_{s\in S}N(\rho,s)\) and \(N(c,S)=\cup_{s\in S}N(c,s)\)
In other words \(N(\rho,k)\) is the set of indices of those rows of \(R\) which do not contain symbol \(k\) and \(N(c,k)\) is the set of indices of those columns of \(R\) which do not contain symbol \(k\).
\[def1130\] An \(n\)-Ryser idempotent \(r\times r\) latin rectangle \(R\) is Type if and only if there exist \(n\)-semi-critical symbols \(l\in [r]\), \(m\in [n]\backslash [r]\) and a subset of symbols \(S\subseteq [n]\) such that (\[def11301\]), (\[def11302\]) and (\[def11303\]) hold.
\[def11301\] \(((([n]\backslash [r])\backslash\{m\})\cup\{l\})\subseteq S\)
\[def11302\] \(r|S|-R(S)=(n-r)(|S|-1)\)
\[def11303\] \(|N(\rho,S)|=|S|-1\)
\[def1140\] An \(n\)-Ryser idempotent \(r\times r\) latin rectangle \(R\) is Type if and only if there exists an \(n\)-semi-critical symbol \(l\in [n]\backslash [r]\), a symbol \(m\in [n]\backslash [r]\), \(r+1\leq l,m\leq n\) and a subset of symbols \(S\subseteq [n]\) such that (\[def11301\]), (\[def11302\]) and (\[def11303\]) hold.
\[def11301\] \(([n]\backslash [r])\backslash\{m\}\subseteq S\)
\[def11302\] \(r|S|-R(S)=(n-r)(|S|-1)\)
\[def11303\] \(|N(\rho,S)|=|S|-1\)
Example \[ex1150\], taken from Andersen (1979), gives an example of a Type \((8,1)\) idempotent \(5\times 5\) latin rectangle.
\[ex1150\] The idempotent \(5\times 5\) latin rectangle \(R\) in Figure \[fig1160\] is Type \((8,1)\). If \(m=8\), \(l=5\) and \(S=\{5,6,7\}\) then \((([n]\backslash [r])\backslash\{m\})\cup\{l\}=(([8]\backslash [5])\backslash\{8\})\cup\{5\}=S\). As \(R(S)=R(5)+R(6)+R(7)=3+3+3=9\) it follows that \(r|S|-R(S)=5\times 3-9=6=3\times 2=(n-r)(|S|-1)\). Finally as \(N(\rho,S)=N(\rho,5)\cup N(\rho,6)\cup N(\rho,7)=\{1,2\}\cup\{1,2\}\cup\{1,2\}\) it follows that \(|N(\rho,S)|=2=|S|-1\). Therefore, \(R\) is Type \((8,1)\).
\[\left[\begin{array}{cccccc} 1 & 3 & 4 & 8 & 2 \\ 4 & 2 & 1 & 3 & 8 \\ 5 & 6 & 3 & 1 & 7 \\ 7 & 5 & 2 & 4 & 6 \\ 6 & 7 & 8 & 2 & 5 \end{array}\right]\]
In his thesis Andersen (1979) Andersen proved that Type \((n,1)\) and Type \((n,2)\) Ryser idempotent \(r\times r\) latin rectangles cannot be embedded in latin squares of order \(n\). His proof exploits the graphs \(B(R)\) and \(B^{\star}(R)\). If \(R\) is the \(5\times 5\) Ryser idempotent latin rectangle of order \(8\) in Figure \[fig1160\] then \(B(R)\) and \(B^{\star}(R)\) are the graphs in Figure \[fig1170\].
\(B^{\star}\) and \(B\) for Fig \[fig1160\]
Andersen in his thesis proves Lemma \[lem1180\] which gives necessary and sufficient conditions, in terms of matchings in \(E(B)\) and \(E(B^{\star})\), for a Ryser idempotent \(r\times r\) latin rectangle to be \(n\)-Ryser \(k\)-extendible.
\[lem1180\] An idempotent \(r\times r\) latin rectangle \(R\) is \(n\)-Ryser \(m\)-extendible if and only if \(E(B(R))\) contains a matching \(E_{\gamma}\) of \(\cC\) into \([n]\) and \(E(B^{\star}(R))\) contains a matching \(E_{\rho}\) of \(\cR\) into \([n]\) such that (\[cond11801\])-(\[cond11803\]) hold.
\[cond11801\] \(m\in [n]\) is the end of no edge in \(E_{\gamma}\cup E_{\rho}\).
\[cond11802\] If \(k\in [n]\) is critical then \(k\) is the end of an edge in \(E_{\gamma}\) and the end of an edge in \(E_{\rho}\).
\[cond11803\] If \(k\in [n]\) is semi-critical then \(k\) is the end of an edge in \(E_{\gamma}\) or the end of an edge in \(E_{\rho}\).
Now looking at the graphs in Figure \[fig1170\] it is not too difficult to see that the Ryser idempotent \(5\times 5\) latin rectangle in Figure \[fig1160\] cannot be embedded in a latin square of order \(8\). Neither \(B\) nor \(B^{\star}\) has an appropriate matching for an \(8\)-Ryser \(8\)-extension. In both cases the obstruction is caused by a component of a particular form.
The components of a graph are usually defined as the maximal connected subgraphs of a graph. An alternative definition, found in Cameron (1994), which avoids the concept of a maximal connected subgraph, gives the components of a graph \(G\) as the equivalence classes of the equivalence relation \(\equiv_G\), on \(V(G)\), defined by \(v\equiv_G w\) if and only if \(v\) and \(w\) are the end-vertices of a path in \(G\).
\[def1190\] A path in a graph \(G\) is a sequence \(P=(v_0,e_1,v_1,e_2,\ldots,e_n,v_n)\) where \(v_i\in V(G)\) for all \(i\in [n]^{\star}\), \(e_j\in E(G)\) for all \(j\in [n]\) and \(e_i=v_{i-1}v_i\) for all \(i\in [n]\). The vertices \(v_0\) and \(v_n\) are the end-vertices of \(P\) and \(n\) is the length of \(P\).
\[def1200\] If \(G\) is a graph and \(S\subseteq V(G)\) then the subgraph of induced by is the graph \(\left\langle S \right\rangle=\left\langle G,S \right\rangle\) with vertex-set \(V(\left\langle S \right\rangle)=S\) and edge-set \(E(\left\langle S \right\rangle)=\{e\in E(G)\,|\, e\mbox{ has an end in } S\}\).
\[def1210\] A component of a graph \(G\) is an induced subgraph $S $ of \(G\) where \(S\) is an equivalence class of the relation \(\equiv_G\).
In general, if the edge-set of a graph \(G\) contains a matching of \(A\) into \(B\), where \(A,B\subseteq V(G)\), and \(\Gamma\) is a component of \(G\) then \(E(\Gamma)\) contains a matching of \(V(\Gamma)\cap A\) into \(V(\Gamma)\cap B\). Therefore if \(B\) and \(B^{\star}\) contain matchings \(E_\rho\), \(E_\sigma\) which satisfy Lemma \[lem1180\] it follows that, for every pair of components \(\{\Gamma\triangleleft B,P\triangleleft B^{\star}\}\), the edge-set \(E(\Gamma)\) has a matching \(E_{\gamma}\) of \(V(\Gamma)\cap [n]\) into \(V(\Gamma)\cap \cS\) and the edge-set \(E(P)\) has a matching \(E_{\rho}\) of \(V(\Gamma^{\star})\cap \cC\) into \(V(\Gamma^{\star})\cap [n]\) such that \(E_{\gamma}\) and \(E_{\rho}\) satisify Lemma \[lem1180\].
If \(\Gamma\) is the component \(\left\langle\{\rho_1,\rho_2,\sigma_5,\sigma_6,\sigma_7\}\right\rangle\) of \(B\) and \(P\) is the component \(\left\langle\{\gamma_3,\gamma_4,\sigma_5,\sigma_6,\sigma_7\}\right\rangle\) of \(B^{\star}\) then there is no pair of matchings \(E_{\gamma}\in E(\Gamma)\), \(E_{\rho}\in E(P)\) which satisfy Lemma \[lem1180\]. To prove this suppose that there is such a pair of matchings. Then, as \(6\) and \(7\) are \(8\)-critical symbols and \(5\) is an \(8\)-semi-critical symbol (and \(8\notin\{5,6,7\}\)), it follows from Lemma \[lem1180\] that \(E_{\gamma}\cup E_{\rho}\) contains at least five edges. Two for each of the critical symbols and one for the semi-critical symbol. However it is equally clear that any matching in \(E(\Gamma)\) contains at most two edges and any matching in \(E(P)\) contains at most two edges, therefore \(E_{\gamma}\cup E_{\rho}\) contains at most four edges. This is a contradiction and proves that there is no pair of matchings which satisfies Lemma \[lem1180\] and hence that any Ryser idempotent \(5\times 5\) latin rectangle for which \(B\) and \(B^{\star}\) are as in Figure \[fig1170\] cannot be embedded in an idempotent latin square of order \(8\).
Andersen then proves that, except for those of Type \((n,1)\) or Type \((n,2)\), a Ryser idempotent \(r\times r\) latin rectangle \(R\) is fully \(n\)-Ryser-extendible. He also shows that, if \(n-r\geq 5\) then \(R\) has an \(n\)-Ryser \(m\)-extension which is neither Type \((n,1)\) nor Type \((n,2)\) for some \(m\in [n]\backslash [r]\). This is tantalisingly close to a characterisation of those idempotent \(r\times r\) latin rectangles which can be embedded in an idempotent latin square of order \(n\). Unfortunately it is not true that Type \((n,1)\) and Type \((n,2)\) are the only \(n\)-Ryser idempotent latin rectangles which cannot be embedded in an idempotent latin square of order \(n\). If \(n-r<5\) then there are a number of further types.
The absence of necessary and sufficient conditions for embedding an idempotent \(r\times r\) latin rectangle in a latin square of order \(n\) might make it seem vain to hope for the corresponding embedding result. Remarkably though, this was obtained by Andersen, Hilton and Rodger L. D. Andersen, Hilton, and Rodger (1982) who gave the best possible bound on \(n\), given here in Theorem \[thm1220\], for embedding an \(r\times r\) idempotent latin rectangle in an idempotent latin square.
\[Andersen, Hilton and Rodger @MR83i:05016\] \[thm1220\] An idempotent \(r\times r\) latin rectangle \(R\) can be embedded in some idempotent latin square of order \(n\) if \(n\geq 2r+1\).
Example \[ex1230\] proves that the bound in Theorem \[thm1220\] is best possible in general.
\[ex1230\] Lemma \[lem1077\] implies that the idempotent \(4\times 4\) latin rectangle \(R\) in Figure \[fig1240\] cannot be embedded in an idempotent latin square of order \(8\) because \(2r-n+1=1\) and yet \(r+1=5\) is contained in no cell of \(R\).
\[\left[ \begin{array}{cccc} 1 & 3 & 4 & 6 \\ 7 & 2 & 8 & 1 \\ 2 & 4 & 3 & 7 \\ 3 & 1 & 2 & 4 \end{array}\right]\]
For \(n<2r\) it remains an open problem to give neccessary and sufficient conditions for embedding an idempotent \(r\times r\) latin rectangle in an idempotent latin square of order \(n\). If \(n=2r\), however, Rodger has shown Rodger (1983), that the idempotent Ryser condition is sufficient and, as \(n-2r=0\), this condition has a particularly simple form.
\[Rodger @MR85h:05031, Abuedia @AA, Grant and Rodger @MR2001i:05040\] \[thm1245\] An idempotent \(r\times r\) latin rectangle \(R\) can be embedded in some idempotent latin square of order \(2r\) if and only if \(R(k)\geq 1\) for all \(k\in [n]\)
Originally Rodger proved this result with \(r>16\) as an additional condition. Subsequently his work was extended by Abueida Abuedia (2000), and Grant and Rodger Grant and Rodger (2000) to give Theorem \[thm1245\].
In this section the problem of embedding idempotent latin rectangles was investigated. In such an embedding the entire main diagonal of the latin square is prescribed. Obviously this imposes certain restrictions and the difficulty of obtaining necessary and sufficient conditions for completing an idempotent latin rectangle suggests that these restrictions are tight. In the next section the horizon is broader and prescribed main diagonal embeddings are considered more generally.
2.4 Prescribed Diagonal Embeddings
The twin aims of this section are to present a generalisation of Theorem \[thm1220\] due to Rodger and also to present a remarkable result of Andersen, Häggkvist, Hilton and Poucher about embedding latin rectangles in latin squares which have very nearly completely prescribed main diagonals
It can be shown, and it is not too difficult to see, that an idempotent \(r\times r\) latin rectangle \(R\) can be embedded in an idempotent latin square of order \(n\) if and only if \(R\) can be embedded in a latin square of order \(n\) with the property that each symbol of \([n]\backslash [r]\) occurs in at least one cell of the main diagonal of \(L\) outside \(R\). This point of view allows for an obvious generalisation. Instead of every \(\sigma\in\Sigma\) being contained in at least one cell of the main diagonal of \(L\) outside \(R\) it is natural to ask for embeddings of \(r\times r\) latin rectangles in latin squares of order \(n\) where \(\sigma\) occurs in at least \(f(\sigma)\) cells on the main diagonal of \(L\) outside \(R\) where \(f:\Sigma\rightarrow [n-r]^{\star}\) is only subject to the obvious necessary constraint that \(f(\Sigma)\leq n-r\).
\[def1260\] If \(R\) is an \(r\times r\) latin rectangle on \(\Sigma\) then \(f\) is an external diagonal prescription of order for \(R\) if and only if \(f:\Sigma\rightarrow [n-r]^{\star}\) and \(f(\Sigma)\leq n-r\). An external diagonal prescription \(f\) of order \(n-r\) is complete if and only if \(f(\Sigma)=n-r\), otherwise \(f\) is incomplete
\[def1270\] If \(R\) is an \(r\times r\) latin rectangle on \(\Sigma\) and \(f\) is an external diagonal prescription of order \(n-r\) on \(\Sigma\) then \(R\) is -embedded in a latin square \(L\) of order \(n\) if and only if, for all \(\sigma\in\Sigma\), at least \(f(\sigma)\) cells of the main diagonal of \(L\) outside \(R\) contain symbol \(\sigma\).
Now the problem of characterising those \(r\times r\) idempotent latin rectangles which can be embedded in some idempotent latin square of order \(n\) is analogous to the problem of characterising those idempotent \(r\times r\) latin rectangles which can be \(f\)-embedded in some idempotent latin square of order \(n\) for complete external diagonal prescription \(f\) of order \(n-r\) on \([n]\) such that \(f(k)=1\) for all \(k\in [n-r]\). It was shown in Section \[sec1065\] that this is an open problem. Consequently, there is little hope of solving the wider problem of characterising those \(r\times r\) latin rectangles which can be \(f\)-embedded in some latin square of order \(n\) for general external diagonal prescription \(f\) of order \(n-r\). It is easy, however, to identify the relevant Ryser-type condition for the general problem.
\[lem1290\] If \(R\) is an \(r\times r\) latin rectangle on \(\Sigma\) and \(f\) is an external diagonal prescription of order \(n-r\) then \(R\) can be \(f\)-embedded in some latin square of order \(n\) on \(\Sigma\) only if \(R(\sigma)\geq 2r-n+f(\sigma)\) for all \(\sigma\in\Sigma\).
Suppose \(R\) can be \(f\)-embedded in a latin square \(L\) of order \(n\). Then, because at least \(f(\sigma)\) cells of the main diagonal outside \(R\) contain symbol \(\sigma\in\Sigma\) it follows that \(|L(A,\sigma)|\leq n-r-f(\sigma)\) for all \(\sigma\in \Sigma\). Now, as \(|L(B,\sigma)|=n-r\) and \(|L(R,\sigma)|+|L(A,\sigma)|+|L(B,\sigma)|=n\), it follows that \(|L(R,\sigma)|\geq 2r-n+f(\sigma)\). The result follows because \(R(\sigma)=|L(R,\sigma)|\).
In Section \[sec1065\] it was shown that, despite the completion problem for idempotent latin rectangles being out of reach, the corresponding embedding problem has been solved. It might be hoped that a similar result could be acheived for general external diagonal prescriptions but, in fact, as is shown now in Lemma \[lem1300\], embedding is not generally possible if \(f\) is complete.
\[lem1300\] For every \(r<n\), if \(R\) is an \(r\times r\) latin rectangle then there exists a complete external diagonal prescription \(f\) of order \(n-r\) on \(\Sigma\) such that \(R\) cannot be \(f\)-embedded in any latin square of order \(n\).
Let \(\sigma_K\in\Sigma\) be any symbol which saitisfies \(R(\sigma_K)<r\), and define \(f:\Sigma\rightarrow [n-r]^{\star}\) by \(f(\sigma_K)=n-r\) and \(f(\sigma_k)=0\) for all \(\sigma_k\in\Sigma\backslash \{\sigma_K\}\). Then \(2r-n+f(\sigma_K)=r\) and so, by Lemma \[lem1290\], \(R\) cannot be \(f\)-embedded in a latin square of order \(n\).
A consequence of Lemma \[lem1300\] is that there is no \(n\) such that every \(r\times r\) latin rectangle is \(f\)-embeddable in a latin square of order \(n\) for every external diagonal prescription \(f\) of order \(n-r\).
There are, however, different ways of looking at this problem. First of all the \(f\) of Lemma \[lem1300\] is complete. If incomplete \(f\) are considered then the strongest, and best-possible, result is the remarkable Theorem \[thm1310\] of Andersen, Häggkvist, Hilton and Poucher which says that the Ryser-type condition is sufficient if \(f\) is incomplete.
\[Andersen, Haggkvist, Hilton and Poucher @AHHP\] \[thm1310\] If \(R\) is an \(r\times r\) latin rectangle on \(\Sigma\) and \(f\) is an incomplete external diagonal prescription of order \(n-r\) then \(R\) can be \(f\)-embedded in a latin square of order \(n\) on \(\Sigma\) if and only if \(R(\sigma)\geq 2r-n+f(\sigma)\) for all \(\sigma\in\Sigma\)
An alternative perspective is to ask for a characterisation of those \(r\times r\) latin rectangles which can be \(f\)-embedded in some latin square of order \(n\geq N\) for some \(N\geq r\) and for general external diagonal prescription \(f\) of order \(n-r\). In light of Theorem \[thm1310\] only the complete \(f\) remain of interest. In this direction Theorem \[thm1320\] of Rodger, which takes \(N=2r+1\), is the strongest result.
\[Rodger @MR86a:05025\] \[thm1320\] If \(r\geq 10\), \(n\geq 2r+1\), \(R\) is an \(r\times r\) latin rectangle and \(f\) is a complete external diagonal prescription of order \(n-r\) then \(R\) can be \(f\)-embedded in a latin square of order \(n\) on \(\Sigma\) if and only if (\[thm13201\]), (\[thm13202\]) and (\[thm13203\]) hold.
\[thm13201\] \(R(\sigma)\geq 2r-n+f(\sigma)\) for all \(\sigma\in\Sigma\).
\[thm13202\] If \(R(\sigma)=r\), for some \(\sigma\in\Sigma\), then \(f(\sigma)\neq n-r-1\).
\[thm13203\] If \(R\) is latin square of order \(r\) on \(\Sigma\) and \(n=2r+1\) then \(f(\Sigma)\neq 1\).
Theorem \[thm1320\] is believed to hold for \(r<10\) although there is no published proof. Certainly the exceptional cases given by (\[thm13202\]) and (\[thm13203\]) of Theorem \[thm1320\] are also exceptional cases for \(r<10\), as shown for \(r=3\) in Example \[ex1323\]
\[ex1323\] If \(R\) is the \(3\times 3\) latin rectangle in Figure \[fig1324\] and \(f:[7]\rightarrow [4]^{\star}\) is defined by \(f(1)=3\), \(f(2)=1\) and \(f(3)=f(4)=\ldots =f(7)=0\) then \(R\) cannot be \(f\)-embedded in any latin square of order \(7\) despite the fact that \(n=2r+1\) and \(R(k)\geq 2r-n+f(k)=f(k)-1\) for all \(k\in [7]\).
If \(R\) is the \(3\times 3\) latin rectangle in Figure \[fig1325\] and \(f:[7]\rightarrow [4]^{\star}\) is defined by \(f(1)=f(4)=f(5)=f(6)=1\) and \(f(2)=f(3)=0\) then \(R\) cannot be \(f\)-embedded in any latin square of order \(7\) despite the fact that \(n=2r+1\) and \(R(k)\geq 2r-n+f(k)=f(k)-1\) for all \(k\in [7]\).
\[\left[ \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 5 & 1 \\ 6 & 1 & 7 \end{array} \right]\]
\[\left[ \begin{array}{ccc} 1 & 2 & 3 \\ 2 & 3 & 1 \\ 3 & 1 & 2 \end{array} \right]\]
Theorem \[thm1320\] generalises Theorem \[thm1220\] for \(r\geq 10\). If \(f(\sigma)\leq 1\) for all \(\sigma\in\Sigma\) then condition (\[thm13201\]) is trivial. The remaining conditions are irrelevant because \(f(\Sigma)=0\) and \(f(\sigma)\neq n-r-1\) for all \(\sigma\in \Sigma\) follows as \(r\geq 10\) and \(n\geq 2r+1\).
In this brief section two results were presented which broaden the idea of idempotent embeddings to more general prescribed diagonal embeddings. The focus is narrowed again in Section \[sec1330\] where the consequences of simultaneously imposing symmetry and idempotency are investigated.
2.5 Symmetric prescribed diagonal embeddings
In this section the aim is to consider prescribed diagonal embeddings for symmetric latin rectangles, The most important result of this section is Theorem \[thm1440\] which gives necessary and sufficient conditions for a symmetric latin rectangle \(R\) to be embedded in a symmetric latin square with a prescribed external main diagonal. The main focus of the rest of this thesis is toward generalising this result to give necessary and sufficient conditions for embedding a symmetric latin rectangle \(R\) in a latin square with prescribed external cells, which are not necessarily main diagonal cells. The analogy with edge-colourings of complete graphs is very close in this section.
First the embedding of symmetric idempotent latin rectangles in symmetric idempotent latin squares is considered. In this case it is important to recall Lemma \[lem280\] and Lemma \[lem290\]. In particular, Lemma \[lem280\] implies that if an idempotent latin square of order \(n\) is symmetric then \(n\) is odd. If \(n\) is odd then a natural question to ask is for necessary and sufficient conditions for a symmetric idempotent \(r\times r\) latin rectangle to be embeddable in some symmetric idempotent latin square of order \(n\).
It follows from Lemma \[lem1290\] that a symmetric idempotent \(r\times r\) latin rectangle \(R\) of order \(n\) can be embedded in a symmetric idempotent latin square of order \(n\) only if \(R(k)\geq 2r-n+1\) for all \(k\in [n]\). It was shown, independently by Andersen Lars Døvling Andersen (1982) and by Hoffmann Hoffman (1983), that this condition is also sufficient. In fact their result, Theorem \[thm1440\], is far stronger. It gives necessary and sufficient conditions for a symmetric \(r\times r\) latin rectangle of order \(n\) on \(\Sigma\) to be \(f\)-embeddable in some symmetric latin square of order \(n\) on \(\Sigma\), for \(f\) an external diagonal prescription of order \(n-r\).
From Lemma \[lem1290\] it follows that a symmetric \(r\times r\) latin rectangle \(R\) is \(f\)-embeddable in a symmetric latin square of order \(n\) on \(\Sigma\) only if \(R(\sigma)\geq 2r-n+f(\sigma)\) for all \(\sigma\in\Sigma\). This condition, however, is not sufficient. The possibility exists that the main diagonal of every partial latin square corresponding to the externally diagonally prescribed latin rectangle \((R,f)\) is not be admissible.
\[def1360\] A pair \((R,f)\) is an externally diagonally prescribed latin rectangle of order \(n-r\) on if and only if \(R\) is an \(r\times r\) latin rectangle on \(\Sigma\) and \(f\) is an external diagonal prescription of order \(n-r\) for \(R\).
\[def1370\] A partial latin square corresponding to an externally diagonally prescribed latin rectangle of order on is any partial latin square \(P\) of order \(n\) which satisfies \(P(i,j)=R(i,j)\) for all \((i,j)\in [r]^2\), \(P(i,j)\) is empty for all \((i,j)\in ([n]\backslash [r])^2\) such that \(i\neq j\) and \(d(P,\sigma)=d(R,\sigma)+f(\sigma)\).
\[ex1380\] If \(R\) is the \(3\times 3\) latin rectangle in Figure \[fig1390\] and \(f:[8]\rightarrow [5]^{\star}\) is defined by \(f(1)=1\), \(f(2)=f(3)=2\) and \(f(4)=\ldots =f(8)=0\) then the partial latin square in Figure \[fig1400\] is a partial latin square of order \(8\) corresponding to the externally diagonally prescribed \(3\times 3\) latin rectangle \((R,f)\) of order \(5\).
\[\left[ \begin{array}{ccc} 1 & 2 & 3 \\ 4 & 8 & 1 \\ 7 & 3 & 4 \end{array} \right]\]
\[\left[ \begin{array}{cccccccc} 1 & 2 & 3 & - & - & - & - & - \\ 4 & 8 & 1 & - & - & - & - & - \\ 7 & 3 & 4 & - & - & - & - & - \\ - & - & - & 1 & - & - & - & - \\ - & - & - & - & 2 & - & - & - \\ - & - & - & - & - & 2 & - & - \\ - & - & - & - & - & - & 3 & - \\ - & - & - & - & - & - & - & 3 \end{array} \right]\]
\[def1405\] An externally diagonally prescribed \(r\times r\) latin rectangle \((R,f)\) is embedded in a latin square \(L\) if and only if \(R\) is \(f\)-embedded in \(L\).
\[lem1410\] An externally diagonally prescribed \(r\times r\) latin rectangle can be embedded in a latin square \(n\) if and only every corresponding partial latin square of order \(n\) is completable.
Suppose \((R,f)\) is an externally diagonally prescribed \(r\times r\) latin rectangle of order \(n\) on \(\Sigma\) embedded in a latin square \(L\) of order \(n\) on \(\Sigma\). Then, by definition, the \(r\times r\) latin rectangle \(R\) is \(f\)-embedded in \(L\). It follows that \(d(L,\sigma)=d(R,\sigma)+f(\sigma)\). Therefore if \(P\) is the partial latin square defined by \(P(i,j)=L(i,j)\) if and only if \((i,j)\in [r]^2\), \(P(i,i)=L(i,i)\) for all \(i\in [n]\backslash [r]\) and \(P(i,j)\) is empty for all \((i,j)\in ([n]\backslash [r])^2\) such that \(i\neq j\), then \(P\) is a partial latin square of order \(n\) corresponding to \((R,f)\). The result follows because every partial latin square can be obtained from \(P\) by interchanging rows and columns outside \(R\).
By Lemma \[lem320\] a symmetric partial latin square corresponding to a symmetric externally diagonally prescribed \(r\times r\) latin rectangle can be embedded in some latin square only if the main diagonal is admissible. This fact has implications for the admissibility of externally diagonally prescribed latin rectangles.
\[def1420\] A symmetric externally diagonally prescribed \(r\times r\) latin rectangle \((R,f)\) on \(\Sigma\) is -admissible if and only if \(f(\sigma)+d(R,\sigma)\equiv n\bmod{2}\) for all \(\sigma\in\Sigma\).
\[def1430\] An externally diagonally prescribed \(r\times r\) latin rectangle \((R,f)\) on \(\Sigma\) is -Ryser if and only if \(R(\sigma)\geq n-2r+f(\sigma)\) for all \(\sigma\in\Sigma\).
\[Andersen @MR86a:05021, Hoffman @MR84h:05024\] \[thm1440\] An externally diagonally prescribed symmetric \(r\times r\) latin rectangle \((R,f)\) on \(\Sigma\) can be embedded in some symmetric latin square of order \(n\) on \(\Sigma\) if and only if \((R,f)\) is \(n\)-Ryser and \(n\)-admissible.
When it comes to embedding a symmetric latin rectangle with a prescribed main diagonal another useful point of view is the graph theoretic one. It was shown in Section \[sec885\] that a symmetric latin rectangle \(R\) can be associated with an edge-coloured complete graph \(\cG\). Under this correspondance the main diagonal cells of \(R\) correspond to loops of \(\cG\). Therefore an embedded externally diagonally prescribed latin rectangle \((R,f)\) corresponds to an embedding of \(\cG\) in an edge-coloured complete graph with prescribed colours on loops. Moreover, embedding \(\cG\) with prescribed colours on loops is the same as embedding the edge-coloured graph made up of edge-coloured components, one of which is \(\cG\) and the rest of which are edge-coloured free-loops.
In general a graph is free-type if it is the union of components each of which is isomorphic to a complete graph of order \(1\) or of order at least \(3\) or is isomorphic to a complete simple graph of order \(2\) (a free-edge). This may seem an unusual class of graphs at the moment but this class is relevant in this thesis because it incorporates the class of graphs which correspond to those partial latin squares which consist of a latin rectangle \(R\) and prescribed cells outside \(R\).
\[def1450\] Graphs \(G\) and \(H\) are isomorphic if and only if there is a bijection (an isomorphism) \(\phi:V(G)\rightarrow V(H)\) with the property that \(vw\in E(G)\) if and only if \(\phi(v)\phi(w)\in E(H)\). The notation \(G\equiv H\) is used if and only if \(G\) and \(H\) are isomorphic.
\[def1460\] A graph \(G\) is -free-type if and only if \(G=G^{\star}\cup G_1\cup G_2\cup\ldots\cup G_k\) for some \(k\geq 1\) where \(G^{\star}\) is isomorphic to \(\Krl\) for some \(r\geq 0\) and \(G_i\) is either isomorphic to \(K_2\) or \(K_1^{l}\) for all \(i\in [k]\).
\[ex1480\] The graph in Figure \[fig1490\] is \(3\)-free-type.
A \(3\)-free-type graph
\[def1500\] If \(G\) is a free-type graph then a component of \(G\) isomorphic to \(K_2\) is a free-edge of \(G\) and a component isomorphic to \(K_1^l\) is a free-loop of \(G\).
\[def1505\] If \(G\) is a free-type graph then \(F(G)=\{\eps\,|\,\eps\mbox{ is a free-edge of }G\}\) and \(\Lambda(G)=\{\lambda\,|\,\lambda\mbox{ is a free-loop of }G\}\)
The next example illustrates the correspondance between symmetric idempotent latin rectangles with prescribed diagonals and edge-coloured free-type graphs.
\[ex1510\] The edge-coloured \(4\)-free-type graph \(\cG\) in Figure \[fig1530\] corresponds to the symmetric idempotent partial latin square \(L\) of order \(7\) in Figure \[fig1520\]. In turn \(L\) corresponds to the symmetric idempotent latin \(4\times 4\) latin rectangle \(R\) defined by \(R(i,j)=L(i,j)\) for all \((i,j)\in [4]^2\). Therefore, if \(f\) is defined as \(f(k)=1\) if \(k\in\{5,6,7\}\) and \(f(k)=0\) if \(k\in\{1,2,3,4\}\), then the externally diagonally prescribed \(4\times 4\) latin rectangle \((R,f)\) of order \(7\) can be embedded in a symmetric latin square of order \(7\) if and only if \(\cG\) can be embedded in a \(7\)-edge-coloured complete graph of order \(7\).
\[\left[ \begin{array}{ccccccc} 1 & 4 & 6 & 5 & - & - & - \\ 4 & 2 & 1 & 3 & - & - & - \\ 6 & 1 & 3 & 7 & - & - & - \\ 5 & 3 & 7 & 4 & - & - & - \\ - & - & - & - & 5 & - & - \\ - & - & - & - & - & 6 & - \\ - & - & - & - & - & - & 7 \end{array}\right]\]
A \(7\)-edge-coloured \(4\)-free-type graph.
Edge-coloured free-type graphs without any free-edges are the edge-coloured graphs which have the closest correspondance with those symmetric partial latin squares which in turn correspond to externally diagonally prescribed symmetric latin rectangles.
\[def1550\] The edge-coloured graph corresponding to an externally diagonally prescribed symmetric latin rectangle \((R,f)\) of order \(n-r\) is the edge-coloured graph corresponding to every partial latin square corresponding to \((R,f)\)
\[lem1560\] The edge-coloured graph corresponding to an externally diagonally prescribed \(r\times r\) latin rectangle \((R,f)\) on \(\Sigma\) is a proper \(\Sigma\)-edge-coloured \(r\)-free-type graph of order \(n\) with no free edges.
By definition, if \(\cG=(G,\phi)\) is the edge-coloured graph corresponding to \((R,f)\) then \(V(G)=\{v_i\,|\,i\in [n]\}\) and \(E(G)=\{v_iv_j\,|\, R(i,j)\mbox{ is filled}\}\). It follows, as \(R(i,j)\) is filled for all \((i,j)\in [r]^2\), that \(G\) has a complete subgraph \(G^{\star}\) of order \(r\) with vertex-set \(\{v_i\,|\,i\in [r]\}\). Moreover, as \(R(i,j)\) is empty for all \((i,j)\in [r]\times [n]\backslash [r]\), \(v_i\in V(G^{\star})\) is the end of no edge \(v_iv_j\) with \(v_j\in V(G)\backslash V(G^{\star})\). Therefore \(G^{\star}\) is a component of \(G\).
As \(R(i,i)\) is filled for all \(i\in [n]\) it follows that \(\{G_i\,|\,i\in [n-r]\}\), where \(G_i=(v_i,v_iv_i)\) for all \(i\in [n-r]\), is a set of subgraphs of \(G\) and because \(L(i,j)\) is empty for all \((i,j)\in [n-r]\times [n]\backslash\{i\}\) it follows that \(G_i\) is a component of \(G\) for all \(i\in [n-r]\).
Now, by definition, \(\phi(v_iv_j)=L(i,j)\) for all \((i,j)\in [n]^2\) such that \((i,j)\) is a filled cell of \(L\). Therefore \(\phi\) is proper because \(L\) has the latin property.
\[lem1570\] The externally diagonally prescribed \(r\times r\) latin rectangle \((R,f)\) of order \(n-r\) on \(\Sigma\) can be embedded in some latin square of order \(n\) if and only if the edge-coloured graph corresponding to \((R,f)\) can be embedded in some proper \(\Sigma\)-edge-coloured complete graph of order \(n\).
Suppose \((R,f)\) can be embedded in a latin square \(L\) of order \(n\). Let \(\cH=(H,(\Sigma,\phi))\) be the edge-coloured graph corresponding to \((R,f)\) and let \(\cG=(G,(\Sigma,\psi))\) be defined by \(G=\Knl\) and \(\phi(v_iv_j)=L(i,j)\) for all \((i,j)\in [n]^2\). Then \(\cG\) is a proper \(\Sigma\)-edge-coloured complete graph of order \(n\) in which \(\cH\) is embedded.
Now suppose \(\cH\) can be embedded in a proper \(\Sigma\)-edge-coloured complete graph \(\cG=(G,(\Sigma,\psi))\) of orderr \(n\). Let \(L\) be defined by \(L(i,j)=\sigma\) if and only if \(\psi(v_iv_j)=\sigma\). Then \(L\) is a latin square of order \(n\) in which \(R\) is \(f\)-embedded.
References
Hall, M. 1945. “An Existence Theorem for Latin Squares.” Bull. Amer. Math. Soc. 51: 387–88.
Evans, T. 1960. “Embedding Incomplete Latin Rectangles.” Amer. Math. Monthly 67: 958–61.
Cruse, Allan B. 1974. “On Embedding Incomplete Symmetric Latin Squares.” J. Combinatorial Theory Ser. A 16: 18–22.
Andersen, Lars Døvling. 1982. “Embedding Latin Squares with Prescribed Diagonal.” In Algebraic and Geometric Combinatorics, 65:9–26. North-Holland Math. Stud. Amsterdam: North-Holland.
Hoffman, D. G. 1983. “Completing Incomplete Commutative Latin Squares with Prescribed Diagonals.” European J. Combin. 4 (1): 33–35.
Lindner, Charles C., and Trevor Evans. 1977. Finite Embedding Theorems for Partial Designs and Algebras. Les Presses de l’Université de Montréal, Montreal, Que.
Andersen, L. D. 1979. “Latin Squares and Their Generalizations.” PhD thesis, University of Reading.
Cameron, P. J. 1994. Combinatorics : Topics, Techniques, Algorithms. Cambridge University Press.
Andersen, L. D., A. J. W. Hilton, and C. A. Rodger. 1982. “A Solution to the Embedding Problem for Partial Idempotent Latin Squares.” J. London Math. Soc. (2) 26 (1): 21–27.
Rodger, C. A. 1983. “Embedding Incomplete Idempotent Latin Squares.” In Combinatorial Mathematics, X (Adelaide, 1982), 1036:355–66. Lecture Notes in Math. Berlin: Springer.
Abuedia, A. 2000. “The Full Embedding Problem.” PhD thesis, Auburn University.
Grant, C., and C. A. Rodger. 2000. “An \(n\) to \(2n\) Embedding of Incomplete Idempotent Latin Squares for Small Values of \(n\).” Discrete Math. 211 (1-3): 53–74.