%04/07/2012 \documentclass[12pt]{article} \usepackage{e-jc} \usepackage{amsthm,amsmath,amssymb} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \title{Biembeddings of metacyclic groups and triangulations of orientable surfaces by complete graphs} \author{M. J. Grannell\\ \small Department of Mathematics and Statistics \\[-0.8ex] \small The Open University \\[-0.8ex] \small Walton Hall\\[-0.8ex] \small Milton Keynes MK7 6AA\\[-0.8ex] \small United Kingdom\\ \small \texttt{m.j.grannell@open.ac.uk} \and M. Knor\thanks{Supported by Slovak research grants VEGA 1/0871/11 and APVV-0223-10.}\\ \small Department of Mathematics \\[-0.8ex] \small Faculty of Civil Engineering\\[-0.8ex] \small Slovak University of Technology\\[-0.8ex] \small Radlinsk\' eho 11 \\[-0.8ex] \small 813 68 Bratislava\\[-0.8ex] \small Slovakia\\ \small \texttt{knor@math.sk} } \date{\dateline{March 25, 2012}{July 4, 2012}\\ \small Mathematics Subject Classifications: 05B15, 05C10} \begin{document} \maketitle \begin{abstract} For each integer $n\ge 3$, $n\ne 4$, for each odd integer $m\ge 3$, and for any $\lambda\in\mathbb{Z}_n$ of (multiplicative) order $m'$ where $m'\mid m$, we construct a biembedding of Latin squares in which one of the squares is the Cayley table of the metacyclic group $\mathbb{Z}_m\ltimes_{\lambda}\mathbb{Z}_n$. This extends the spectrum of Latin squares known to be biembeddable. The best existing lower bounds for the number of triangular embeddings of a complete graph $K_z$ in an orientable surface are of the form $z^{z^2(a-o(1))}$ for suitable positive constants $a$ and for restricted infinite classes of $z$. Using embeddings of $\mathbb{Z}_3\ltimes_{\lambda}\mathbb{Z}_n$, we extend this lower bound to a substantially larger class of values of $z$. \bigskip\noindent \textbf{Keywords:} triangular embedding; Latin square; complete graph; complete tripartite graph; metacyclic group \end{abstract} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Introduction} In proving Heawood's conjecture in the late 1960s, Ringel and Youngs \cite{R,Y} constructed one triangular embedding of a complete graph $K_z$ in a nonorientable surface for every $z\equiv 0,1$ (mod 3), $z\ge 9$, and one triangular embedding of $K_z$ in an orientable surface for every $z\equiv 0,3,4,7$ (mod 12), $z\ge 3$. It was subsequently shown that there are large numbers of such embeddings. Korzhik and Voss obtained $a\cdot 2^{bz}$ nonisomorphic triangular embeddings of complete graphs $K_z$ ($a$ and $b$ being positive constants) in both the orientable and nonorientable cases, providing that $z$ is sufficiently large, see \cite{K1, K2, KV1, KV2, KV3}. Better bounds were obtained for some classes of values of $z$ using orientable embeddings of complete tripartite graphs and product constructions; these produce face $2$-colourable triangular embeddings of $K_z$. Face 2-colourability requires $z\equiv 1,3,7,9$ (mod 12) in the nonorientable case, and $z\equiv 3,7$ (mod 12) in the orientable case. In the papers \cite{BGGS, GGS} (see also \cite{GGs} for a survey) the authors constructed $a\cdot 2^{bz^2}$ nonisomorphic triangular embeddings of $K_z$ ($a$ and $b$ being positive constants) in both the orientable and nonorientable cases, provided that $z$ is sufficiently large and lies in certain congruence classes. As mentioned in \cite{GKor}, an upper bound for the number of nonisomorphic triangular embeddings of $K_z$ is $z^{z^2/3}$. By modifying the product construction for complete tripartite graphs, in \cite{GG, GGK, GKor} the authors obtained a lower bound of the form $z^{az^2}$ (where $a$ is a positive constant) for certain sparse but infinite classes of values of $z$, these classes comprising values $z_s$ that are exponential in $s$. These results can be summarized as follows: \begin{theorem} \label{thm:re_sparse} Suppose that $z=m(t-1)\alpha(s)+1$ where $t\equiv 3,7\pmod{12}$, $t\ge 7$, $m$ is odd, $m>1$, and $\alpha(s)=3(2^{2s+1}-1)$ in the orientable case (respectively, $\alpha(s)=2^s$ in the nonorientable case). Then, as $s\to\infty$, there are at least $$ z^{z^2\big(\frac{t-3}{96m^2(t-1)}-o(1)\big)} $$ nonisomorphic face 2-colourable triangular embeddings of $K_z$ in an orientable (respectively, nonorientable) surface. \end{theorem} Further triangular embeddings of complete graphs in both orientable and nonorientable surfaces for other sparse classes where $z_s$ is exponential in $s$ and the bound is $z^{z^2(a-o(1))}$ can be found in \cite{GK;JGT}. For nonorientable surfaces, Theorem~{\ref{thm:re_sparse}} was further improved in \cite{GKlinear} and we obtained a linear class of $z$'s achieving the very same bound: \begin{theorem} \label{thm:re_linear} Suppose that $z=2ms(t-1)+1$ where $t\equiv 3,7\pmod{12}$, $t\ge7$, and that either $s\equiv 1\pmod 6$ and $m\equiv 3,5\pmod 6$, or $s\equiv 5\pmod 6$ and $m\equiv 1,3\pmod 6$. Then, as $s\to\infty$, there are at least $$ z^{z^2\big(\frac{t-3}{96m^2(t-1)}-o(1)\big)} $$ nonisomorphic face 2-colourable triangular embeddings of $K_z$ in a nonorientable surface. \end{theorem} Theorem~{\ref{thm:re_linear}} was obtained by using face $2$-colourable triangular embeddings of complete tripartite graphs; these are equivalent to biembeddings of Latin squares. The key step was to construct such a biembedding in which one of the Latin squares is the Cayley table of a dihedral group. At the present time we are unable to give an analogous statement for orientable surfaces. However, using a biembedding of Latin squares in which one of the squares is the Cayley table of the semidirect product of cyclic groups, $\mathbb{Z}_3\ltimes_{\lambda}\mathbb{Z}_n$, where $\lambda$ has order $3$ in $\mathbb{Z}_n$, we are able to construct $z^{z^2(a-o(1))}$ triangular embeddings of $K_{z}$ in an orientable surface for an infinite sequence $\{z_s\}$, such that $|\{z_s\le n\}|\ge c\frac n{\log n}$ for a positive constant $c$. This is shown in Corollary~{\ref{cor:three}} below, while a more general result is given in Corollary~{\ref{cor:Kn_m}}. To obtain our results, we further generalize the product construction using so-called nonstandard bridging described in \cite{GG, GK;JGT}. In a particular instance of this construction we give a precise description of the Latin squares involved which generalizes the result given in \cite{GGK}. By this means, biembeddings of Latin squares are constructed, in which one of the squares is a Cayley table of $\mathbb{Z}_m\ltimes_{\lambda}\mathbb{Z}_n$, $m$ being odd, thereby extending the spectrum of Latin squares known to be biembeddable. As mentioned above, a main ingredient is the construction of many differently labelled triangular embeddings of the complete regular tripartite graph $K_{w,w,w}$. The next section is devoted to such graphs. Complete graphs are dealt with in the subsequent section. The colours of a face 2-colourable triangular embedding are always taken to be black and white. The reader is referred to \cite{GT} for terminology undefined in the paper. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Complete tripartite graphs} Suppose that $\rho$ is a face 2-colourable triangular embedding of $K_{n,n,n}$. As shown in \cite{Glasg}, such an embedding is necessarily in an orientable surface. If the tripartition of $K_{n,n,n}$ is taken to define the row, column and entry labels of an $n\times n$ array, then in each of the two colours, every prescribed pair of row and column labels is in a triangle with a unique entry label; every pair of row and entry labels is in a triangle with a unique column label; and every pair of column and entry labels is in a triangle with a unique row label. Hence, the triangles of each colour class determine a Latin square. Denote by $R$ and $R'$ the two Latin squares obtained from $\rho$ in this way. Then we say that $R$ \emph{biembeds} with $R'$ and we write $R\bowtie R'$. With a slight abuse of notation we also write $\rho=R\bowtie R'$. The triangles corresponding to $R$ will be taken to be coloured white, while those corresponding to $R'$ will be taken to be black. Let $R$ be a Latin square of order $r$. A \emph{transversal} in $R$ is a set of $r$ distinct entry labels occurring in $r$ distinct rows and $r$ distinct columns. In an embedding $\rho=R\bowtie R'$, a transversal in $R$ ($R'$) corresponds to a \emph{parallel class} of faces, i.e., to a set of $r$ vertex disjoint triangles coloured white (black). In \cite{GGS}, see also \cite{GGK}, there is a product construction which creates a face 2-colourable triangular embedding of $K_{mn,mn,mn}$ from face 2-colourable triangular embeddings of $K_{n,n,n}$ and $K_{m,m,m}$. We now recall a simplified form of this construction. Take $m$ copies of a face 2-colourable triangular embedding of $K_{n,n,n}$, $\varphi_t=L\bowtie L'$, $0\le t\le m-1$, $m>1$. These embeddings have identical sets of white (black) triangles. To be able to distinguish the vertices of these triangular embeddings, suppose that the vertex set of $\varphi_t$ is $R_t\cup C_t\cup E_t$, where $R_t=\{r_0^t,r_1^t,\dots,r_{n-1}^t\}$, $C_t=\{c_0^t,c_1^t,\dots,c_{n-1}^t\}$ and $E_t=\{e_0^t,e_1^t,\dots,e_{n-1}^t\}$ are the three sets forming the tripartition of $K_{n,n,n}$. We assume that the vertices of $R_t$, $C_t$ and $E_t$ correspond to rows, columns and entries, respectively, of both $L$ and $L'$. For each $t$, $0\le t\le m-1$, $(r_i^t,c_j^t,e_k^t)$ is a white (black) triangle of $\varphi_t$ if and only if the triple $(r_i^0,c_j^0,e_k^0)$ is a white (black) triangle of $\varphi_0$ . Now take $n^2$ copies of a face 2-colourable triangular embedding of $K_{m,m,m}$, $\psi_{i,j}=Q\bowtie Q'$, $0\le i,j\le n-1$, in which the square $Q'$ has a transversal $\mathcal T$, corresponding to a parallel class of black triangles in $\psi_{i,j}$. We suppose that the vertex set of $\psi_{i,j}$ is $R^*\cup C^*\cup E^*$, where $R^*=\{r^*_0,r^*_1,\dots,r^*_{m-1}\}$, $C^*=\{c^*_0,c^*_1,\dots,c^*_{m-1}\}$ and $E^*=\{e^*_0,e^*_1,\dots,e^*_{m-1}\}$ are the three sets forming the tripartition of $K_{m,m,m}$. We assume that the vertices of $R^*$, $C^*$ and $E^*$ correspond to rows, columns and entries, respectively, of both $Q$ and $Q'$. Suppose that the parallel class of black triangles, common to all $\psi_{i,j}$, is $\mathcal T=\{(r^*_{\alpha_t},c^*_{\beta_t},e^*_{\gamma_t});\,0\le t\le m-1\}$, where $\alpha$, $\beta$ and $\gamma$ are suitable permutations of $\{0,1,\dots,m-1\}$. There is no need to distinguish the vertices of $\psi_{i_1,j_1}$ from those of $\psi_{i_2,j_2}$, because in the final embedding of $K_{mn,mn,mn}$ only the names of vertices appearing in $\varphi_t$, $0\le t\le m-1$, will be used. Consider one white triangle of $\varphi_0$, say $(r_i^0,c_j^0,e_k^0)$, and cut out this triangle from $\varphi_0$ and its copies $(r_i^t,c_j^t,e_k^t)$ from $\varphi_t$, $1\le t\le m-1$. This results in $m$ surfaces with $m$ disjoint boundaries. Similarly, cut out the $m$ black triangles $(r^*_{\alpha_t},c^*_{\beta_t},e^*_{\gamma_t})$ of the parallel class $\mathcal T$ from the map $\psi_{i,j}$. Observe that the indices $i$ and $j$ of $\psi_{i,j}$ are the same as the indices of the vertices $r^0_i$ and $c^0_j$. Now glue the boundaries of $(r_i^t,c_i^t,e_i^t)$ and $(r^*_{\alpha_t},c^*_{\beta_t},e^*_{\gamma_t})$, $0\le t\le m-1$, so that $r^*_{\alpha_t}$, $c^*_{\beta_t}$ and $e^*_{\gamma_t}$ are identified with $r_i^t$, $c_j^t$ and $e_k^t$, respectively. Repeat the procedure with each of the white triangles of $\varphi_0$ in turn. At each subsequent step after the first, cutting out the white triangles leaves a single surface but still with $m$ disjoint boundaries. Denote the resulting embedding by $\rho$. The names of vertices of $\rho$ are inherited from $\varphi_t$, $0\le t\le m-1$, so that the resulting embedded graph is tripartite with tripartition $\cup_{t=0}^{m-1}R_t$, $\cup_{t=0}^{m-1}C_t$ and $\cup_{t=0}^{m-1}E_t$. Every edge $r_i^0c_j^0$, $r_i^0e_k^0$ or $c_j^0e_k^0$ is in a unique white triangle in $\varphi_0$, say $(r_i^0,c_j^0,e_k^0)$. Hence, for every $s$ and $t$, $0\le s,t\le m-1$ and $s\ne t$, the edge $r_i^sc_j^t$ ($r_i^se_k^t$, $c_j^se_k^t$) is added just once in the construction, namely when gluing $\psi_{i,j}$. Thus the underlying graph of the triangular embedding is the complete tripartite graph $K_{mn,mn,mn}$. Observe that the triangular embedding $\rho$ is face 2-colourable because the holes in $\varphi$'s come from white triangles while those in $\psi$'s come from black triangles. Consequently, $\rho$ triangulates an orientable surface. The following result from \cite{GGK} gives an easy description of the two Latin squares involved in $\rho$. \begin{theorem} \label{thm:sq_constr} Suppose that $L\bowtie L'$, where $L$ and $L'$ are Latin squares of order $n$, and suppose also that $Q\bowtie Q'$, where $Q$ and $Q'$ are Latin squares of order $m$ and the square $Q'$ has a transversal $\mathcal T$. Define $Q(L)$ and $Q'(L,\mathcal T,L')$, Latin squares of order $mn$, with row, column and entry labels $\{0,1,\dots,mn-1\}$, so that for every $u$, $v$, $i$ and $j$, $0\le u,v\le m-1$ and $0\le i,j\le n-1$, we have \begin{eqnarray*} Q(L)(nu+i,nv+j) &=& nQ(u,v)+L(i,j),\\ Q'(L,T,L')(nu+i,nv+j) &= & nQ'(u,v)+k, \end{eqnarray*} \[\mbox{where } k=\left\{\begin{array}{ll} L(i,j)&\mbox{if $(r_u,c_v,e_w)\not\in\mathcal T$ for any $w$,} \\ L'(i,j)&\mbox{if there exists $w$ such that $(r_u,c_v,e_w)\in\mathcal T$.} \end{array} \right.\] Then $Q(L)\bowtie Q'(L,\mathcal T,L')$. \end{theorem} The embedding $Q(L)\bowtie Q'(L,\mathcal T,L')$ is isomorphic to $\rho$ described above. The square $Q(L)$ is partitioned into $n\times n$ subsquares which are just relabelled copies of $L$. The square $Q'(L,\mathcal T,L')$ has a similar structure but the subsquares corresponding to the transversal $\mathcal T$ are relabelled copies of $L'$. Note that if $L'$ has a transversal, then among the relabelled copies of $L'$ one can find a transversal in $Q'(L,\mathcal T,L')$. This feature facilitates re-application of the construction. Observe that if $Q$ and $L$ are Cayley tables of groups $\mathcal Q$ and $\mathcal L$, represented respectively on $\{0,1,\dots,m-1\}$ and $\{0,1,\dots,n-1\}$, then $Q(L)$ is the Cayley table of the direct product $\mathcal Q\times\mathcal L$ represented on $\{0,1,\dots,mn-1\}$. Using the product construction described above, in \cite{GK} we showed that the Cayley table of each Abelian group, with the single exception of $\mathcal C_2^2$, appears in a biembedding of Latin squares. In this paper we present an analogous result for certain metacyclic groups. To do this, we change the gluing process in the product construction. Suppose that the Latin square $L$ contains a subsquare $K$ of order $k$. For notational convenience, assume that this subsquare contains the rows $0,1,\dots,k-1$, columns $0,1,\dots,k-1$ and entries $0,1,\dots,k-1$, so that $K(a,b)=L(a,b)$, $0\le a,b\le k-1$. Denote by $P$ the set of $k^2$ white triangles corresponding to this subsquare of $L$ in $\varphi_0=L\bowtie L'$. Next choose $m-1$ permutations $\pi_1,\pi_2,\dots,\pi_{m-1}$ of $\{0,1,\dots,k-1\}$. We change the gluing process on the triangles of $P$ using column permutations $\pi_t$, $1\le t\le m-1$. As previously, cut out all the white triangles of $\varphi_t$, $0\le t\le m-1$, and cut out all the black triangles of the transversals $\mathcal T$ in all $\psi_{i,j}$, $0\le i,j\le m-1$. If $(r_i^0,c_j^0,e_k^0)$ is a white triangle of $\varphi_0$ which does not belong to $P$, then do the gluing as above. However, if $(r_a^0,c_b^0,e_{K(a,b)}^0)$ is any one of the $p^2$ triangles of $P$, then take $\psi_{a,b}$ and identify $(r^*_{\alpha_0},c^*_{\beta_0},e^*_{\gamma_0})$ with $(r_a^0,c_b^0,e_{K(a,b)}^0)$, as earlier, while for $t$ with $1\le t\le m-1$, identify $(r^*_{\alpha_t},c^*_{\beta_t},e^*_{\gamma_t})$ with $(r_a^t,c_{\pi_t(b)}^t,e_{K(a,\pi_t(b))}^t)$. Clearly, such an identification leads to face 2-colourable triangular embedding in a surface. The question is, what is the underlying graph? We show that it is $K_{mn,mn,mn}$. Obviously, if $(r_i^0,c_j^0,e_k^0)$ is a triangle which is not in $P$, then in the resulting embedding, exactly as previously, we have edges $r_i^sc_j^t$, $r_i^se_k^t$ and $c_j^se_k^t$ for all $s$ and $t$. So consider the case when $(r_i^0,c_j^0,e_k^0)$ is a triangle of $P$. Clearly these edges are present when $s=t$ since they appear in the embedding $\varphi_s$. When $s\ne t$ and $0\le s,t\le m-1$, the following table describes how these edges are formed. To simplify the notation, we define $\pi_0$ to be the identity. \begin{description} \item[$r_x^sc_y^t$:] $\psi_{x,\pi^{-1}_t(y)}$ connects $(r_x^s,c_{\pi_s(\pi_t^{-1}(y))}^s,e_{K(x,\pi_s(\pi_t^{-1}(y)))}^s)$ with $(r_x^t,c_y^t,e_{K(x,y)}^t)$. \item[$r_x^se_y^t$:] Denote by $z$ a value, $0\le z\le k-1$, such that $K(x,z)=y$. Then $\psi_{x,\pi_t^{-1}(z)}$ connects $(r_x^s,c_{\pi_s(\pi_t^{-1}(z))}^s,e_{K(x,\pi_s(\pi_t^{-1}(z)))}^s)$ with $(r_x^t,c_z^t,e_y^t)$. \item[$c_x^se_y^t$:] Denote by $z$ a value, $0\le z\le k-1$, such that $K(z,\pi_t(\pi_s^{-1}(x)))=y$. Then $\psi_{z,\pi_s^{-1}(x)}$ connects $(r_z^s,c_x^s,e_{K(z,x)}^s)$ with $(r_z^t,c_{\pi_t(\pi_s^{-1}(x))}^t,e_y^t)$. \end{description} Hence, every edge of $K_{mn,mn,mn}$ appears at least once. It is obvious that no edge can appear more than once due to the fact that the original gluing procedure led to an embedding of $K_{mn,mn,mn}$ and the number of edges created by the new gluing process is the same as that for the original. Let us call this gluing on triangles of $P$ \emph{nonstandard}, while the gluing mentioned before {Theorem \ref{thm:sq_constr}} we will call \emph{standard}. We remark that a simplified version of nonstandard gluing, when $K$ is a cyclic square and all permutations $\pi_t$ are identities, $0\le t\le m-2$, while $\pi_{m-1}(x)=x+1\pmod k$, was considered in \cite{GK;JGT}. Now we state a result which interprets the above construction in terms of Latin squares in the case when $K=L$. Using relabellings, there are many pairs of Latin squares that can be used to represent an embedding. Theorem~{\ref{thm:nsq_constr}} gives, what appears to us, the most useful representation. \begin{theorem} \label{thm:nsq_constr} Suppose that $L\bowtie L'$, where $L$ and $L'$ are Latin squares of order $n$, and suppose also that $Q\bowtie Q'$, where $Q$ and $Q'$ are Latin squares of order $m$ and the square $Q'$ has a transversal $\mathcal{T}$. Suppose that for each $t$, $1\le t\le m-1$, $\pi_t$ is a permutation of $\{0,1,\dots,n-1\}$, and let $\pi_0$ be the identity permutation on the same set. Define $A$ and $A'$, Latin squares of order $mn$ with row, column and entry labels $\{0,1,\ldots,mn-1\}$, such that for each $u$, $v$, $i$ and $j$, $0\le u,v \le m-1$ and $0\le i,j\le n-1$, we have \begin{eqnarray*} A(nu+i,nv+j)&=&nQ(u,v)+L(i,\pi_{\gamma_w^{-1}}(\pi_{\beta_v^{-1}}^{-1}(j))), \mbox{ where $w=Q(u,v)$}\\ A'(nu+i,nv+j)&=&nQ'(u,v)+k, \end{eqnarray*} \[\mbox{where } k=\left\{\begin{array}{ll} L'(i,j)&\mbox{if there exists $w$ such that $(r_u,c_v,e_w)\in\mathcal{T}$}\\ L(i,\pi_{\gamma_w^{-1}}(\pi_{\beta_v^{-1}}^{-1}(j)))& \mbox{otherwise (here $w=Q'(u,v)$).} \end{array} \right.\] Then $A\bowtie A'$. \end{theorem} \begin{proof} Throughout the proof and subsequent discussions, we take the triangles determined by $L$, $Q$ and $A$ to be white, and those determined by $L'$, $Q'$ and $A'$ to be black. We use the notation as previously described. For $0\le t\le m-1$, $\varphi_t$ is a copy of $L\bowtie L'$ with row, column and entry labels $r^t_i$, $c^t_i$ and $e^t_i$, where $0\le i\le n-1$. For $0\le i,j\le n-1$, $\psi_{i,j}$ is a copy of $Q\bowtie Q'$ and the triangles of $\mathcal T$ are taken to be $(r^*_{\alpha_u},c^*_{\beta_u},e^*_{\gamma_u})$, where $\alpha$, $\beta$ and $\gamma$ are permutations of $\{0,1,\dots,m-1\}$. Without loss of generality, we may take $\alpha$ to be the identity, i.e., $\alpha_u=u$ for each $u$. For each of the $n^2$ pairs $(i,j)$, we remove the black triangles of $\mathcal T$ from $\psi_{i,j}$ and we remove the white triangles $(r^t_i,c^t_{\pi_t(j)},e^t_{L(i,\pi_t(j))})$ from $\varphi_t$. Then we glue the holes according to the description given above. Since we retain the vertex labelling from the $\varphi$'s, this leads to a relabelling of the triangles contributed by the $\psi_{i,j}$'s in the resulting embedding. For each of the $n^2$ pairs $(i,j)$, we relabel the vertices of $\psi_{i,j}$ so that each row label $r^*_{\alpha_t}$ is renamed as $r^t_i$, each column label $c^*_{\beta_t}$ is renamed as $c^t_{\pi_t(j)}$, and each entry label $e^*_{\gamma_t}$ is renamed as $e^t_{L(i,\pi_t(j))}$. Now consider the triangles of $\rho$. All the white triangles come from $\psi_{i,j}$. Hence the triple $(r^u_{i'},c^v_{j'},e^w_{k'})$ is a white triangle of $\rho$ coming from $\psi_{i,j}$ if and only if $i'=i$, $j'=\pi_v(j)$, $k'=L(i,\pi_w(j))$ and $\gamma_w=Q(\alpha_u,\beta_v)$. On the other hand, a triple $(r^u_{i'},c^v_{j'},e^w_{k'})$ is a black triangle of $\rho$ coming from $\psi_{i,j}$ if and only if $i'=i$, $j'=\pi_v(j)$, $k'=L(i,\pi_w(j))$, $\gamma_w=Q'(\alpha_u,\beta_v)$ and $u\ne v$. The black triangles corresponding to $(r^t_i,c^t_{\pi_t(j)},e^t_{L(i,\pi_t(j)))})$ were cut out from $\psi_{i,j}$ and in their place we have in $\rho$ the black triangles $(r^t_i,c^t_j,e^t_{L'(i,j)})$, which come from $\varphi_t$. Take a typical white triangle of $\rho$ having the edge $\{r^u_i, c^v_j\}$. This triangle comes from the embedding $\psi_{i,\pi_v^{-1}(j)}$, so that the third vertex is $e^w_k$, where $k=L(i,\pi_w(\pi_v^{-1}(j)))$ and $\gamma_w=Q(\alpha_u,\beta_v)$. The black triangles of $\rho$ are of two types: those from the embeddings $\varphi_u$, and those from the embeddings $\psi_{i,j}$. The former have an edge $\{r^u_i,c^u_j\}$, and the third vertex is $e^u_k$ where $k=L'(i,j)$. The latter have an edge $\{r^u_i, c^v_j\}$ where $v \ne u$, and the third vertex is $e^w_k$, where $k=L(i,\pi_w(\pi_v^{-1}(j)))$ and $\gamma_w=Q'(\alpha_u,\beta_v)$. Now we relabel the rows, columns and entries of $\rho$. Define $A$ and $A'$, Latin squares of order $mn$, such that \begin{eqnarray*} A(n\alpha_u+i, n\beta_v+j)=n\gamma_w+k &\Leftrightarrow& (r^u_i,c^v_j,e^w_k)\mbox{ is a white triangle of }\rho\\ A'(n\alpha_u+i, n\beta_v+j)=n\gamma_w+k &\Leftrightarrow& (r^u_i,c^v_j,e^w_k)\mbox{ is a black triangle of }\rho \end{eqnarray*} where $u,v,w \in\{0,1,\ldots,m-1\}$ and $i,j,k\in\{0,1,\ldots,n-1\}$. Then $A \bowtie A'$ is an embedding isomorphic to $\rho$ and \begin{eqnarray*} A(nu+i,nv+j)&=&nQ(u,v)+L(i,\pi_{\gamma_w^{-1}}(\pi_{\beta_v^{-1}}^{-1}(j))), \mbox{ where $w=Q(u,v)$}\\ A'(nu+i,nv+j)&=&nQ'(u,v)+k, \end{eqnarray*} \[\mbox{where } k=\left\{\begin{array}{ll} L'(i,j)&\mbox{if there exists $w$ such that $(r_u,c_v,e_w)\in\mathcal{T}$}\\ L(i,\pi_{\gamma_w^{-1}}(\pi_{\beta_v^{-1}}^{-1}(j)))& \mbox{otherwise (here $w=Q'(u,v)$).} \end{array} \right.\] This completes the proof. \end{proof} \vspace{5mm} Denote by $C_m$ the Cayley table of the cyclic group $\mathbb{Z}_m$, so that $C_m$ consists of the triples $(r_i,c_j,e_{i+j})$ with subscript arithmetic in $\mathbb{Z}_m$. Denote by $C^+_m$ the Latin square obtained from $C_m$ by adding $1$ (modulo $m$) to the subscript of every entry element of $C_m$. In \cite{Glasg} we have the following result. \begin{theorem} \label{thm:cyclic} For each positive integer $m$, $C_m\bowtie C^+_m$. \end{theorem} If $m$ is odd, then $\mathcal T=\{(r_i,c_i,e_{2i+1});\, 0\le i\le m{-}1\}$ is a transversal of $C^+_m$ (the addition in the subscript being modulo $m$). Although the cyclic squares of even order do not have a transversal, in \cite{FP} we have \begin{theorem} \label{thm:gen_cyclic} If $m\ge 3$ and $m\ne 4$ then $C_m\bowtie H_m$ for some Latin square $H_m$ having a transversal. \end{theorem} Consider the embedding $A\bowtie A'$ described in Theorem~{\ref{thm:nsq_constr}}, using the notation of that result. Suppose that $L$ and $L'$ are of order $n$ and that $L\bowtie L'$. Suppose also that $m$ is odd and that $Q=C_m$ and $Q'=C^+_m$, so that by Theorem~{\ref{thm:cyclic}}, we have $C_m\bowtie C^+_m$. Choose the transversal in $C^+_m$ on the main diagonal, i.e., $\mathcal T=(r^*_u,c^*_u,e^*_{2u+1})$, so that $\alpha_u=\beta_u=u$ and $\gamma_u=2u+1$ (mod $m$). Take $\pi$ be a permutation of order $m'$ on the set $\{0,1,\dots,n-1\}$, where $m'\mid m$, and put $\pi_u=\pi^u$ for $1\le u\le m-1$. We concentrate on $A$. Since $\beta_v=v$, we have $\beta_v^{-1}=v$. Thus, $\pi^{-1}_{\beta_v^{-1}}(j)=\pi^{-1}_v(j)=\pi^{-v}(j)$. Furthermore, since $2$ is coprime with $m$, there is $k$ such that $2k\equiv 1\pmod m$. Hence, $\gamma^{-1}_w=k(w-1)$. If $w=u+v+1\pmod m$ then $$ \pi_{\gamma_w^{-1}}(\pi^{-1}_{\beta_v^{-1}}(j))=\pi^{kw-k-v}(j)= \pi^{k(u+v+1)-k-v}(j)=\pi^{ku+(kv-v)}(j). $$ Now relabel the columns of $A$ to obtain $B$, so that $A(nu+i,nv+j)=B(nu+i,nv+\pi^{kv-v}(j))$. Then $$ B(nu+i,nv+j)=n(u\oplus_m v)+L(i,\pi^{ku}(j)), $$ where $\oplus_m$ denotes addition in $\mathbb{Z}_m$. Since $k$ is divisor of $1$ in $\mathbb{Z}_m$, $\pi^k$ is a permutation of order $m'$. Put $\zeta=\pi^k$. Then $$ B(nu+i,nv+j)=n(u\oplus_m v)+L(i,\zeta^u(j)). $$ Observe that $\zeta^2=\pi^{2k}=\pi$, so that $\zeta$ is a square root of $\pi$ and $\pi$ is square of $\zeta$. Now we recall the definition of a semidirect product of two groups $\mathcal G=(G;\circ)$ and $\mathcal H=(H;*)$, of orders $m$ and $n$ respectively. Suppose that there exists a homomorphism $\xi:\,\mathcal G\to Aut(\mathcal H)$. Then the semidirect product $\mathcal G\ltimes_{\xi}\mathcal H$ is a group defined on $G\times H$ so that for every $u,v\in G$ and $i,j\in H$ we have $(u,i)\cdot(v,j)=(u\circ v,i*\xi_u(j))$. We remark that many authors define the semidirect product with the order of coordinates reversed and denote it by $\mathcal H\rtimes_{\xi}\mathcal G$. However the order we use emerges naturally from the construction described above. We will restrict ourselves to the case when $\mathcal G = (\mathbb{Z}_m;\oplus_m)$ and $\mathcal H= (\mathbb{Z}_n;\oplus_n)$. Then $\mathcal G\ltimes_{\xi}\mathcal H$ is an example of a \emph{metacyclic} group. Put $\xi_1=\zeta$ so that $\xi_k=\zeta^k$, $0\le k\le m-1$, and consequently $\xi_{m'}=\zeta^{m'}=\pi^{2m'}=(\pi^{m'})^2$ is the identity. Thus $\zeta$ is an automorphism of $\mathcal H= (\mathbb{Z}_n; \oplus_n)$ of order $m'$ such that $m'\mid m$. Since $\mathcal H= (\mathbb{Z}_n;\oplus_n)$, every automorphism $\zeta$ of $\mathcal{H}$ is of the form $\zeta(x)=\lambda x$, where $\lambda\in\mathbb{Z}_n$ is coprime with $n$. In this case $\lambda$ determines $\zeta$ and hence also $\xi$, and vice-versa. Consequently, we can write $\ltimes_{\lambda}$ instead of $\ltimes_{\xi}$. The automorphism $\zeta(x)=\lambda x$ has order $m'$ if and only if $m'$ is the (multiplicative) order of $\lambda$ modulo $n$. If $\lambda=1$ then $\zeta$ and $\xi$ are identities and $\mathcal G\ltimes_{\lambda}\mathcal H$ is the direct product $\mathcal G\times\mathcal H$. The following result is an important consequence of Theorem~{\ref{thm:nsq_constr}}. It extends the spectrum of Latin squares known to be biembeddable. For given $n$ and $m$ it generalizes the results of \cite{GGK} since for $\lambda=1$ we get the direct product of $\mathbb{Z}_n$ with $\mathbb{Z}_m$. The squares involved in Theorem~{\ref{thm:semi}} turn out to be very useful. \begin{theorem} \label{thm:semi} Suppose that $n\ge 3$, $n\ne 4$, and that $m\ge 3$ is odd. Suppose also that $\lambda \in \mathbb{Z}_n$ is coprime with $n$ and has order $m'$ where $m'\mid m$. Form a semidirect product $\mathbb{Z}_m\ltimes_{\lambda} \mathbb{Z}_n$, so that for every $u,v\in\mathbb{Z}_m$ and $i,j\in\mathbb{Z}_n$ we have $(u,i)\cdot(v,j)=(u\oplus_m v,i\oplus_n\lambda^uj)$. Denote by $B$ the Cayley table of $\mathbb{Z}_m\ltimes_{\lambda}\mathbb{Z}_n$. Then $B\bowtie B'$ for some Latin square $B'$ having a transversal. \end{theorem} \begin{proof} Set $\zeta(x)=\lambda x$ for $x\in\mathbb{Z}_n$, $\pi=\zeta^2$, and put $\pi_u=\pi^u$, $1\le u\le m-1$. Further, let $L=C_n$ and $L'=H_n$, where $C_n\bowtie H_n$ is the embedding guaranteed by Theorem~{\ref{thm:gen_cyclic}}. Finally, set $Q=C_m$, $Q'=C^+_m$ and let $\mathcal T$ be the transversal in $C^+_m$ given by $\{(r^*_u,c^*_u,e^*_{2u+1});\,0\le u\le m-1\}$. Then construct the embedding $A\bowtie A'$ described in Theorem~{\ref{thm:nsq_constr}}. Since $H_n$ has a transversal, among the copies of $H_n$ in $A'$ one can find a transversal in $A'$. Now relabel the columns of $A$ and $A'$ by the same permutation, so that $A$ is transformed to the square $B$ described immediately before the statement of Theorem~{\ref{thm:semi}}. Then $$ B(nu+i,nv+j)=n(u\oplus_m v)+C_n(i,\lambda^uj) =n(u\oplus_m v)+i\oplus_n\lambda^uj. $$ Thus $B$ is the Cayley table of $\mathbb{Z}_m\ltimes_{\lambda}\mathbb{Z}_n$, when the pair $(u,i)$, $0\le u\le m-1$ and $0\le i\le n-1$, is represented as an integer $nu+i$ from the interval $[0,mn-1]$. \end{proof} \vspace{5mm} One reason for constructing biembeddings of Latin squares in which one of the squares is the Cayley table of $\mathbb{Z}_m\ltimes_{\lambda}\mathbb{Z}_n$, is that this Cayley table often has a cubic number of $C_m$-subsquares. We establish conditions for this in the next theorem. This feature can then be exploited to provide estimates of the numbers of various biembeddings. If $\lambda$ has order $m'>1$ where $m'\mid m$, we have $\lambda\ne 1$ and $\lambda^m=1$, and consequently $\sum_{\ell=0}^{m-1}\lambda^{\ell}=0$ in $\mathbb{Z}_n$. It can happen that $\sum_{\ell=0}^{m-1}\lambda^{\ell}=0$ in $\mathbb{Z}_n$ even when $\lambda=1$; this will be the case when $m$ is a multiple of $n$ and in such a case $\mathbb{Z}_m\ltimes_{\lambda}\mathbb{Z}_n$ is just the direct product $\mathbb{Z}_m\times\mathbb{Z}_n$. Our next two theorems are predicated on this sum being zero, although our main interest is in the case when $\lambda\ne 1$. If $\sum_{\ell=0}^{m-1}\lambda^{\ell}=0$ in $\mathbb{Z}_n$ then it is certainly the case that $\lambda^m=1$ and so $\lambda$ has order $m'$ for some $m'\mid m$. \begin{theorem} \label{thm:many} Suppose that $m,n\ge 2$ and that $B$ is a Cayley table of the metacyclic group $\mathbb{Z}_m\ltimes_{\lambda}\mathbb{Z}_n$, defined by $\lambda\in\mathbb{Z}_n$ where $\sum_{\ell=0}^{m-1}\lambda^{\ell}=0$ in $\mathbb{Z}_n$. Then there are $n^3$ different $m\times m$ subsquares $S$ of $B$, each isotopic to $C_m$. Moreover, for every $u,v$, $0\le u,v\le m-1$, each such subsquare $S$ has exactly one triple of the form $(r_{nu+i},c_{nv+j},e_{nw+k})$ for some $i$, $j$ where $nw+k=B(nu+i,nv+j)$, $0\le w\le m-1$ and $0\le i,j,k\le n-1$. \end{theorem} \begin{proof} First choose $a_0$, $b_0$ and $b_1$ such that $0\le a_0,b_0,b_1\le n-1$. There are $n^3$ possible choices for $(a_0,b_0,b_1)$. Define \begin{displaymath} \begin{array}{rll} \vspace{1mm} a_u\!\!\!\!&=a_0+(b_1-\lambda b_0)\sum_{\ell=0}^{u-1}\lambda^{\ell}& \mbox{ for $u\ge 1$;}\\ \vspace{1mm} b_v\!\!\!\!&=b_0+(b_1-b_0)\sum_{\ell=0}^{v-1}\lambda^{\ell}& \mbox{ for $v\ge 2$;}\\ d_w\!\!\!\!&=a_0+(b_1-\lambda b_0)\sum_{\ell=0}^{w-1}\lambda^{\ell} +\lambda^wb_0& \mbox{ for $w\ge 1$;} \end{array} \end{displaymath} and $d_0=a_0+b_0$, all arithmetic being in $\mathbb{Z}_n$. Observe that \begin{displaymath} \begin{array}{rl} \vspace{1mm} d_m\!\!\!\!&=a_0+\lambda^m b_0=a_0+b_0=d_0,\mbox{~~and for $w\ge 1$}\\ \vspace{1mm} d_{m+w}\!\!\!\!&=a_0+(b_1-\lambda b_0)\sum_{\ell=0}^{w-1}\lambda^{\ell} + (b_1-\lambda b_0)\lambda^w\sum_{\ell=w}^{m+w-1}\lambda^{\ell-w} + \lambda^w \lambda^m b_0 =d_w. \end{array} \end{displaymath} Hence, for every $w$ we have $d_{m+w}=d_w$. We will now show that $B(nu+a_u,nv+b_v)=n(u\oplus_m v)+d_{u\oplus_m v}$ for $0\le u,v\le m-1$. This will establish that the $m\times m$ subarray of $B$ defined by the rows $r_{nu+a_u}$ and the columns $c_{nv+b_v}$ is indeed a Latin square isotopic to $C_m$ and with exactly one triple of the form $(r_{nu+i},c_{nv+j},e_{nw+k})$ for each $(u,v)$. To prove this we must show that $a_u\oplus_n\lambda^u b_v=d_{u\oplus_m v}$. We assume first that $u\ge 1$ and $v\ge 2$. Then \begin{eqnarray*} a_u\oplus_n\lambda^u b_v &=&a_0+(b_1-\lambda b_0)\sum_{\ell=0}^{u-1}\lambda^{\ell} +\lambda^u\bigg(b_0+(b_1-b_0)\sum_{\ell=0}^{v-1}\lambda^{\ell}\bigg)\\ &=& a_0+(b_1-\lambda b_0)\sum_{\ell=0}^{u+v-1}\lambda^{\ell}+\lambda^{u+v} b_0\\ &=& d_{u+v}=d_{u\oplus_m v}, \end{eqnarray*} with arithmetic in $\mathbb{Z}_n$. The remaining cases when $u=0$ or $v=0,1$ are left to the reader. \end{proof} \vspace{5mm} We say that a set $S$ of $C_m$-subsquares of a Latin square $B$ is an \emph{independent set of $C_m$-subsquares} if no two elements of $S$ share a common triple. Note that this independence relates to triples and not to row, column or entry labels. Now we could use Theorem~2.5 of \cite{GK;JGT} to obtain a large number of independent sets of $C_m$-subsquares in $B$. However, since the squares described in the proof of Theorem~{\ref{thm:many}} have a special pattern, we can obtain a better bound. \begin{theorem} \label{thm:indep_sets} Suppose that $m,n\ge 2$ and that $B$ is a Cayley table of the metacyclic group $\mathbb{Z}_m\ltimes_{\lambda}\mathbb{Z}_n$, defined by $\lambda\in\mathbb{Z}_n$ where $\sum_{\ell=0}^{m-1}\lambda^{\ell}=0$ in $\mathbb{Z}_n$. Then the number of distinct independent sets of $C_m$-subsquares in $B$ is at least $$ \Big(m^2n+1\Big)^{\big(\frac{n^2}{m^2}-1\big)}. $$ \end{theorem} \begin{proof} We consider only Latin $C_m$-subsquares of $B$ described in the proof of Theorem~{\ref{thm:many}}. We first show that for given $u$ and $v$ $(0\le u,v\le m-1)$ and given $a_u$ and $b_v$ $(0\le a_u,b_v\le n-1)$, there are precisely $n$ of these $C_m$-subsquares that contain the triple $(r_{nu+a_u}, c_{nv+b_v}, e_{nw+d_w})$, where $nw+d_w=B(nu+a_u,nv+b_v)$. This is obviously true if $u=v=0$ since there are $n$ choices for $b_1$. It will follow in the general case if it can be shown that the values of $a_u,b_v$ and $b_{v+1}$ determine $a_0, b_0$ and $b_1$. (Here, if $v=m-1$ then $v+1$ is taken to be 0.) From the expression for $b_v$ we have $b_{v+1}-b_v=(b_1-b_0)\lambda^v$ (for all $v$ including $v=m-1$). So $b_1-b_0=(b_{v+1}-b_v)\lambda^{-v}$. Combining this with the expression for $b_v$ gives \[b_0=b_v-(b_{v+1}-b_v)\lambda^{-v}\sum_{\ell=0}^{v-1}\lambda^{\ell}.\] Then $b_1=b_0+(b_{v+1}-b_v)\lambda^{-v}$ gives \[b_1=b_v-(b_{v+1}-b_v)\lambda^{-v}\bigg(\sum_{\ell=0}^{v-1}\lambda^{\ell}-1\bigg).\] Finally, the expression for $a_u$ gives \[a_0=a_u-(b_1-\lambda b_0)\sum_{\ell=0}^{u-1}\lambda^{\ell},\] where $b_0$ and $b_1$ are already determined above. Thus $a_u,b_v$ and $b_{v+1}$ determine $a_0, b_0$ and $b_1$. Now suppose that $P$ is the set of triples of a $C_m$-subsquare of $B$. Since $P$ has $m^2$ triples, a triple of $P$ occurs in at most $m^2 n$ of the $C_m$-subsquares of $B$ having the form described in the proof of Theorem~{\ref{thm:many}}. Denote by $I_q$ the number of independent sets of these $C_m$-subsquares that contain exactly $q$ of these $C_m$-subsquares. By Theorem~{\ref{thm:many}}, we have $$ I_q\ge n^3\big(n^3-m^2n\big)\big(n^3-2m^2n\big)\dots\big(n^3-(q-1)m^2n\big)\Big/q!. $$ Put $Q=\big\lfloor\frac{n^2}{m^2}\big\rfloor$. Then from the above we deduce $$ I_q\ge \Big(m^2n\Big)^q Q\big(Q-1\big)\big(Q-2\big)\dots\Big(Q-(q-1)\Big)\Big/q!= \big(m^2n\big)^q\binom Qq. $$ Of course, if $q>Q$ then we have just the trivial bound $I_q\ge 0$. Now summing $I_q$ for all $q\le Q$ gives the bound on the number of independent sets of $C_m$-subsquares as $$ \sum_{q=0}^Q I_q\ge \sum_{q=0}^Q \Big(m^2n\Big)^q\binom Qq =\Big(m^2n+1\Big)^Q\ge \Big(m^2n+1\Big)^{\big(\frac{n^2}{m^2}-1\big)}. $$ \vspace{-6mm} \end{proof} \vspace{5mm} Theorems {\ref{thm:many}} and \ref{thm:indep_sets} require that $\lambda$ satisfies $\sum_{\ell=0}^{m-1}\lambda^{\ell}=0$ in $\mathbb{Z}_n$. We will concentrate on the case $m=3$. This equation then becomes $\lambda^2+\lambda+1=0$. Since we aim to construct orientable embeddings of $K_z$, we assume that $n$ is odd. In such a case the equation has a solution if and only if $-3$ is a square in $\mathbb{Z}_n$. The following three theorems can be used to determine when this happens. \begin{theorem}[{\cite[Theorem 96]{HW}}] \label{thm:Hardy} $-3$ is quadratic residue (i.e., a non-zero square modulo $p$) of every prime $p$ of the form $p=6k+1$, but it is not quadratic residue of any prime $p$ of the form $p=6k+5$. \end{theorem} \begin{theorem}[{\cite[Theorem~5.30]{Apo}}] \label{thm:Apo_powers} Let $p$ be a prime number and $\alpha\ge 2$. Suppose that $f(x)$ is a polynomial with integer coefficients, such that $f(x)\equiv 0\pmod{p^{\alpha-1}}$ has a solution $r$. If $f'(r)\not\equiv 0\pmod p$ then there is a solution of $f(x)\equiv 0\pmod{p^\alpha}$. \end{theorem} \begin{theorem}[{\cite[Theorem~5.28]{Apo}}] \label{thm:Apo_general} Let $n=n_1 n_2 \dots n_t$, where $n_1,n_2,\dots,n_t$ are relatively prime, and suppose that $f(x)$ is a polynomial with integer coefficients. Then the congruence $f(x)\equiv 0\pmod n$ has a solution if and only if each of the congruences $f(x)\equiv 0\pmod{n_i}$, $1\le i\le t$, has a solution. \end{theorem} With the aid of these three theorems, we can determine when $-3$ is a square in $\mathbb{Z}_n$. \begin{theorem} \label{thm:solution-3} Suppose that $n$ is odd and that $n=p_1^{\alpha_1}p_2^{\alpha_2}\dots p_t^{\alpha_t}$ is its factorization into prime powers where $p_11$. In such a case $p_i\ne 3$, so that $p_i=6k_i+1$. Let $x_i$ be a solution of $f(x)=x^2+3\equiv 0\pmod{p_i}$ as guaranteed above. Since $p_i>3$, we have $x_i\ne 0$. Hence, $f'(x_i)=2x_i\not\equiv 0\pmod{p_i}$ because $2$ and $n$ are coprime. By Theorem~{\ref{thm:Apo_powers}}, there is a solution of $x^2+3\equiv 0\pmod{p_i^2}$. Using the same argument repeatedly we find that there is a solution of $x^2+3\equiv 0\pmod{p_i^{\alpha_i}}$. Thus, for every $i$, $1\le i\le t$, there is a solution of $x^2+3\equiv 0\pmod{p_i^{\alpha_i}}$. Since $p_1^{\alpha_1},p_2^{\alpha_2},\dots,p_t^{\alpha_t}$ are relatively prime, Theorem~{\ref{thm:Apo_general}} guarantees a solution of $x^2+3\equiv 0\pmod n$. \end{proof} \vspace{5mm} Now the question is: what is the proportion of numbers $n$ satisfying Theorem~{\ref{thm:solution-3}}? Clearly there is not a linear class of these numbers. Let $N$ denote the number of integers $n$ having the form described in Theorem~{\ref{thm:solution-3}} which are at least $7$ and at most $n^*$. The following table gives an indication of the value of $N$ for low values of $n^*$. \[ \begin{tabular}{|c|c|} \hline $n^*$ & $N$\\ \hline 1\,000 & 150 \\ 3\,000 & 424 \\ 10\,000 & 1\,331 \\ 30\,000 & 3\,769 \\ \hline \end{tabular} \] \vspace{3mm} By the strong version of Dirichlet's theorem on arithmetic progressions, see for example \cite[page 154]{Apo}, the number of primes of the form $6k+1$, which are not greater than $n^*$, is asymptotically equal to $n^*/(2\log n^*)$. Hence, for any constant $c>2$ and $n^*$ sufficiently large, there are at least $n^*/(c\log n^*)$ numbers $n$ not exceeding $n^*$ and satisfying the assumptions of Theorem~{\ref{thm:solution-3}}. This provides an asymptotic lower bound for $N$. \vskip 5mm Now we return to the embedding $B\bowtie B'$ described in Theorem~{\ref{thm:semi}}, where $B$ is the Cayley table of the metacyclic group $\mathbb{Z}_m\ltimes_{\lambda}\mathbb{Z}_n$. Here $n\ge 3$, $n\ne 4$, $m\ge 3$ is odd, $\lambda \in \mathbb{Z}_n$ is coprime with $n$ and has order $m'$ where $m'\mid m$. We will assume that $\sum_{\ell=0}^{m-1}\lambda^{\ell}=0$ in $\mathbb{Z}_n$; this ensures that $B$ has many independent sets of $C_m$-subsquares. Recall also that $B'$ has a transversal. We will apply a product construction using the embeddings $B\bowtie B'$ and $C_{\ell}\bowtie C^+_{\ell}$, the latter taken from Theorem~{\ref{thm:cyclic}}. Here we only consider the special case $\ell=m$. This will give a face 2-colourable triangular embedding of the complete tripartite graph $K_{w,w,w}$ where $w=m^2n$. Let $\mathcal T$ be a transversal in $C^+_m$ and let $I$ be an independent set of $C_m$-subsquares in $B$. On white triangles which do not belong to a square in $I$ we glue copies of $C_m\bowtie C^+_m$ through $\mathcal T$ in a standard way, while on white triangles which do belong to a square in $I$ we glue copies of $C_m\bowtie C^+_m$ through $\mathcal T$ in a nonstandard way as explained before Theorem \ref{thm:nsq_constr}. For every square $S$ in $I$, for the nonstandard gluing we set $\pi_1,\pi_2,\dots,\pi_{m-2}$ to be the identity and $\pi_{m-1}$ to be a column permutation defined by $\pi_{m-1}(j_i)=j_{i+1}$, where $c_{j_0},c_{j_1},\dots,c_{j_{m-1}}$ are the columns of $S$ in the natural order and the addition in the index is modulo $m$. Theorem \ref{thm:dif_labeled} below establishes that different independent sets, $I$ and $I'$, of \linebreak $C_m$-subsquares in $B$ give rise to differently labelled face 2-colourable triangular embeddings of the resulting complete tripartite graph. There are two ways in which $I$ and $I'$ can differ. Firstly, there may be a triple $(r_i,c_j,e_k)$ of some $C_m$-subsquare lying in $I$ which is not a triple of any $C_m$-subsquare lying in $I'$, or vice-versa. If this is not the case then every triple covered by $I$ is also covered by $I'$ and vice-versa, but these triples are partitioned into different $C_m$-subsquares. In this latter case there will be $C_m$-subsquares $S$ and $S'$, lying in $I$ and $I'$ respectively, with $S\ne S'$, but both containing a common triple $(r_i,c_j,e_k)$. \begin{theorem} \label{thm:dif_labeled} Suppose that $n\ge 3$, $n\ne 4$, that $m\ge 3$ is odd, and that $B$ is a Cayley table of the metacyclic group $\mathbb{Z}_m\ltimes_{\lambda}\mathbb{Z}_n$, defined by $\lambda\in\mathbb{Z}_n$ where $\sum_{\ell=0}^{m-1}\lambda^{\ell}=0$ in $\mathbb{Z}_n$. Let $S$ be one of the $C_m$-subsquares described in Theorem~{\ref{thm:many}} with triple $(r_i,c_j,e_k)$. Take $\rho_1$ to be any map obtained from the construction by applying nonstandard gluing to $S$. Take $\rho_2$ to be any map obtained from the construction either by \begin{enumerate} \item[(a)] applying standard gluing to $(r_i,c_j,e_k)$, or \item[(b)] taking another $C_m$-subsquare $S'$ described in Theorem~{\ref{thm:many}} and containing the triple $(r_i,c_j,e_k)$, and applying nonstandard gluing on $S'$. \end{enumerate} Then $\rho_1$ and $\rho_2$ are differently labelled face $2$-colourable triangular embeddings of \linebreak $K_{m^2n,m^2n,m^2n}$. Moreover, both $\rho_1$ and $\rho_2$ have an identically labelled parallel class of black triangles. \end{theorem} \begin{proof} We use the labelling of vertices of $\varphi_t$ and $\psi_{i,j}$ described above, taking $\mathcal T=\{(r^*_{\alpha_t},c^*_{\beta_t},e^*_{\gamma_t}):\,0\le t\le m-1\}$. Using the notation of the proofs of Theorems~{\ref{thm:many}} and {\ref{thm:indep_sets}}, we may take $i=nu+a_u$, $j=nv+b_v$ and $k=n(u\oplus_m v)+d_{u+v}$. Consider the map $\psi_{i,j}$ where $0\le i,j\le p-1$. In $\psi_{i,j}$ there is a black triangle $(r^*_{\alpha_{(m-1)}},c^*_{\beta_{(m-1)}},e^*_{\gamma_{(m-1)}})$, and this triangle is adjacent to a white triangle \linebreak $(r^*_{\alpha_{(m-1)}},c^*_{\beta_{(m-1)}},e^*_{\gamma_q})$ for some $q$, $0\le q2$ and $w^*$ sufficiently large, there are at least $w^*/(9c\log w^*)$ numbers $w$ not exceeding $w^*$ and satisfying the assumptions of Corollary~{\ref{cor:no_tripartite}}. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% \section{Complete graphs} We now turn our attention to face 2-colourable triangular embeddings of complete graphs. The following result can be deduced from \cite[Construction~5]{GGS} and \cite[Theorem~3.1]{GG}, see also \cite[Theorem~3.1]{GK;JGT}. \begin{theorem} \label{thm:no_complete} Suppose that $t\equiv 1,3,7,9 \pmod{12}$ and $w\equiv 0,1,3,4 \pmod 6$, where at least one of $w$ and $\frac{t-1}2$ is odd. Moreover, suppose that there is a face 2-colourable triangular embedding of $K_t$, a face 2-colourable triangular embedding of $K_{2w+1}$, and that there are $r$ differently labelled face 2-colourable triangular embeddings of $K_{w,w,w}$, all having an identically labelled parallel class of black triangles. Then there are at least $$ r^{\frac{(t-1)(t-3)}6} $$ differently labelled face 2-colourable triangular embeddings of $K_{w(t-1)+1}$. If either the embedding of $K_t$ or that of $K_{2w+1}$ is nonorientable, then the embeddings of $K_{w(t-1)+1}$ are nonorientable. If the embeddings of both $K_t$ and $K_{2w+1}$ are orientable, then the embeddings of $K_{w(t-1)+1}$ are orientable. \end{theorem} It was shown by Ringel \cite{R} that for $t\equiv 3\pmod{12}$, and by Youngs \cite{Y} that for $t\equiv 7\pmod{12}$, there exists a face $2$-colourable triangular embedding of $K_t$ in an orientable surface. The statement $2w+1\equiv 3,7\pmod{12}$ is equivalent to $w\equiv 1,3\pmod 6$. Hence, we have the following corollary of Theorems~{\ref{thm:no_tripartite}} and \ref{thm:no_complete}. \begin{corollary} \label{cor:Kn_m} Suppose that $z=m^2n(t-1)+1$, where $t\equiv 3, 7 \pmod{12}$, $m^2n\equiv 1,3\pmod 6$, $m,n\ge 3$, and there exists $\lambda$ such that $\sum_{\ell=0}^{m-1}\lambda^{\ell}=0$ in $\mathbb{Z}_n$. Then there are at least $$ \frac{(m^2n+1)^{\big(\frac{n^2}{m^2}-1\big)\big(\frac{(t-1)(t-3)}6\big)}}{z!} $$ nonisomorphic face $2$-colourable triangular embeddings of $K_z$ in an orientable surface. \end{corollary} For large $n$ the expression in Corollary~{\ref{cor:Kn_m}} is $z^{z^2\big(\frac{t-3}{6m^6(t-1)}-o(1)\big)}$. The best bound is obtained when $m=3$. By Corollary~{\ref{cor:no_tripartite}} we obtain the following result. \begin{corollary} \label{cor:three} Suppose that $z=9n(t-1)+1$ where $t\equiv 3,7 \pmod{12}$, $n$ is odd, and $n$ is not divisible by $9$ and not divisible by any prime of the form $6k+5$. Then, as $n\to\infty$, there are at least $$ z^{z^2\big(\frac{t-3}{4374(t-1)}-o(1)\big)} $$ nonisomorphic face $2$-colourable triangular embeddings of $K_z$ in an orientable surface. \end{corollary} The bound in Corollary~{\ref{cor:three}} is better when $t$ is large, but in such a case the class of corresponding values $z$ is more sparse. Fix $t$ such that $t\equiv 3$ or $7\pmod{12}$. Then for every $c>2$ and $z^*$ sufficiently large, there are at least $z^*/(9c(t-1)\log z^*)$ numbers $z$ not exceeding $z^*$ and satisfying the assumptions of Corollary ~{\ref{cor:three}}. Using the approach explained in this paper one can also construct a large number of nonorientable embeddings of complete graphs $K_z$. However, this method does not yield a linear class of values $z$ satisfying the bound, and the bound itself is not as good as the current best bound for the nonorientable case presented in \cite{GKlinear}, which does apply to a linear class of values of $z$. \vskip 1pc \noindent{\bf Acknowledgement}~~Part of this work was done when the second author was visiting the first author and he thanks him for his hospitality. \begin{thebibliography}{99} \bibitem{Apo} T. M. Apostol. \newblock \emph{Introduction to Analytic Number Theory}. \newblock Springer, Berlin, 1976. \bibitem{BGGS} C. P. Bonnington, M. J. Grannell, T. S. Griggs, and J. \v Sir\'a\v n. \newblock Exponential families of non-isomorphic triangulations of complete graphs. \newblock \emph{J. Combin. Theory Ser. B}, 78:169--184, 2000. \bibitem{GGs} M. J. Grannell and T. S. Griggs. \newblock Designs and Topology. \newblock In \emph{Surveys in combinatorics}, volume 346 of \emph{London Mathematical Society Lecture Notes Series}, pages 121--174. Cambridge University Press, 2007. \bibitem{GG} M. J. Grannell and T. S. Griggs. \newblock A lower bound for the number of triangular embeddings of some complete graphs and complete tripartite graphs. \newblock \emph{J. Combin. Theory Ser. B}, 98:637--650, 2008. \bibitem{Glasg} M. J. Grannell, T. S. Griggs, and M. Knor. \newblock Biembeddings of Latin squares and Hamiltonian decompositions. \newblock \emph{Glasg. Math. J.}, 46:443--457, 2004. \bibitem{GGK} M. J. Grannell, T. S. Griggs, and M. Knor. \newblock On biembeddings of Latin squares. \newblock \emph{Electronic J. Combin.}, 16:R106, 12pp, 2009. \bibitem{GGS} M. J. Grannell, T. S. Griggs, and J. \v Sir\'a\v n. \newblock Recursive constructions for triangulations. \newblock \emph{J. Graph Theory}, 39:87--107, 2002. \bibitem{GK} M. J. Grannell and M. Knor. \newblock Biembeddings of Abelian groups. \newblock \emph{J. Combin. Des.}, 18:71--83, 2010. \bibitem{GKor} M. J. Grannell and M. Knor. \newblock A lower bound for the number of orientable triangular embeddings of some complete graphs. \newblock \emph{J. Combin. Theory Ser. B}, 100:216--225, 2010. \bibitem{GK;JGT} M. J. Grannell and M. Knor. \newblock On the number of trianguar embeddings of complete graphs and complete tripartite graphs. \newblock \emph{J. Graph Theory}, 69:370--382, 2012. \bibitem{GKlinear} M. J. Grannell and M. Knor. \newblock Dihedral biembeddings and triangulations by complete and complete tripartite graphs. \newblock \emph{Graphs Combin.}, to appear. \bibitem{FP} M. J. Grannell and M. Knor. \newblock Biembedding Abelian groups with mates having transversals. \newblock \emph{J. Combin. Des.}, 20:81--88, 2012. \bibitem{GT} J. L. Gross and T. W. Tucker. \newblock \emph{Topological Graph Theory}. \newblock John Wiley, New York, 1987. \bibitem{HW} G. H. Hardy and E. M. Wright. \newblock \emph{The Theory of Numbers}. \newblock Clarendon Press, Oxford, 1960. \bibitem{K1} V. P. Korzhik. \newblock Exponentially many nonisomorphic orientable triangular embeddings of $K_{12s}$. \newblock \emph{Discrete Math.}, 308:1046--1071, 2008. \bibitem{K2} V. P. Korzhik. \newblock Exponentially many nonisomorphic orientable triangular embeddings of $K_{12s+3}$. \newblock \emph{Discrete Math.}, 309:852--866, 2009. \bibitem{KV1} V. P. Korzhik and H.-J. Voss. \newblock On the number of nonisomorphic orientable regular embeddings of complete graphs. \newblock \emph{J. Combin. Theory Ser. B}, 81:58--76, 2001. \bibitem{KV2} V. P. Korzhik and H.-J. Voss. \newblock Exponential families of nonisomorphic non-triangular orientable genus embeddings of complete graphs. \newblock \emph{J. Combin. Theory Ser. B}, 86:186--211, 2002. \bibitem{KV3} V. P. Korzhik and H.-J. Voss. \newblock Exponential families of nonisomorphic nonorientable genus embeddings of complete graphs. \newblock \emph{J. Combin. Theory Ser. B}, 91:253--287, 2004. \bibitem{R} G. Ringel. \newblock \emph{Map color theorem}. \newblock Springer-Verlag, New York and Berlin, 1974. \bibitem{Y} J. W. T. Youngs. \newblock The mystery of the Heawood conjecture. \newblock In \emph{Graph Theory and its Applications}, pages 17--50, Academic Press, New York, 1970. \end{thebibliography} \end{document}