\documentclass[12pt]{article} \usepackage{e-jc} \specs{P4.2}{22(4)}{2015} \usepackage{amsmath} \usepackage{amssymb} \usepackage{amsfonts} \usepackage{amsthm} \usepackage{latexsym} \def\stvorcek{\ensuremath{\square}} \newtheorem{theorem}{Theorem}[section] \newtheorem{corollary}[theorem]{Corollary} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{definition}[theorem]{Definition} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{lema}[theorem]{Lemma} \newtheorem{problem}{Problem} \theoremstyle{definition} \newtheorem{example}{Example} \title{\bf Genus of the cartesian product of triangles} % input author, affilliation, address and support information as follows; % the address should include the country, and does not have to include % the street address \author{Michal Kotrb\v{c}\'ik\\ \small Faculty of Informatics\\[-0.8ex] \small Masaryk University\\[-0.8ex] \small Brno, Czech Republic\\ \small\tt kotrbcik@fi.muni.cz\\ \and Toma\v{z} Pisanski\\ \small FAMNIT\\[-0.8ex] \small University of Primorska\\[-0.8ex] \small Koper, Slovenia\\ \small\tt tomaz.pisanski@upr.si } % \date{\dateline{submission date}{acceptance date}\\ % \small Mathematics Subject Classifications: comma separated list of % MSC codes available from http://www.ams.org/mathscinet/freeTools.html} \date{\dateline{Dec 5, 2012}{Sep 18, 2015}{Oct 16, 2015}\\ \small Mathematics Subject Classifications: 05C10, 05C25, 05--04, 05E18, 20F05, 57M15} \begin{document} \maketitle % E-JC papers must include an abstract. The abstract should consist of a % succinct statement of background followed by a listing of the % principal new results that are to be found in the paper. The abstract % should be informative, clear, and as complete as possible. Phrases % like "we investigate..." or "we study..." should be kept to a minimum % in favor of "we prove that..." or "we show that...". Do not % include equation numbers, unexpanded citations (such as "[23]"), or % any other references to things in the paper that are not defined in % the abstract. The abstract will be distributed without the rest of the % paper so it must be entirely self-contained. \begin{abstract} We investigate the orientable genus of $G_n$, the cartesian product of $n$ triangles, with a particular attention paid to the two smallest unsolved cases $n=4$ and $5$. Using a lifting method we present a general construction of a low-genus embedding of $G_n$ using a low-genus embedding of $G_{n-1}$. Combining this method with a computer search and a careful analysis of face structure we show that $30\le \gamma(G_4) \le 37$ and $133 \le\gamma(G_5) \le 190$. Moreover, our computer search resulted in more than $1300$ non-isomorphic minimum-genus embeddings of $G_3$. We also introduce genus range of a group and (strong) symmetric genus range of a Cayley graph and of a group. The (strong) symmetric genus range of irredundant Cayley graphs of $Z_p^n$ is calculated for all odd primes $p$. \bigskip\noindent \textbf{Keywords:} graph, cartesian product, genus, embedding, triangle, symmetric embedding, Cayley graph, Cayley map, genus range, group \end{abstract} \section{Introduction} Finding the minimum genus of a graph is a very difficult problem from both practical and algorithmic perspective. In general, it is NP-hard to determine the minimum genus even in the class of cubic graphs, see \cite{thomassen:1989}, respectively \cite{thomassen:1997}. While the minimum genus of various specific families of graphs has been calculated in the past, the well-known instance of determining the minimum genus of complete graphs \cite{ringel} indicates the level of difficulty that can be encountered. The genera of hypercubes have been computed by G. Ringel \cite{ringel:1955} and by Beineke and Harary \cite{BH}. Generalizations of these methods were used by A.~T. White to calculate the genus of the cartesian products of even cycles \cite{white:1970}, and later by T. Pisanski for cartesian products of more general graph classes \cite{pisanski:1980, pisanski:1982}. Eventually, these techniques have been used to determine the genus of most abelian and hamiltonian groups and non-orientable genus of some metacyclic groups \cite{PT:1989a,PT:1989b,PW:1988}. In most cases, the developed methods can be adopted to the products where some factors are odd cycles of length at least five. A canonical decomposition theorem for abelian groups states that every abelian group is a direct product $Z_{n_1}\times \cdots \times Z_{n_k}$, where $n_{i}$ divides $n_{i+1}$ for all $i n$. \section{Lower bounds} \label{section:lower-bounds} By $G_n$ we denote the cartesian product of $n$ triangles, that is, $$G_n = \underbrace{K_3\square K_3 \square \cdots \square K_3}_{n\text{-times}}.$$ For a prime $p$, by $Z_p^n$ we denote the direct product of $n$ copies of the cyclic group $Z_p$; clearly, $G_n$ is a Cayley graph of $Z_3^n$. For the number of vertices and edges of $G_n$ we have $|V(G_n)| = 3^n$ and $|E(G_n)| = n3^n$, respectively. The total number of triangles of $G_n$ is denoted by $T(G_n)$; clearly, $T(G_n) = n3^{n-1}$. For an embedding of $G_n$, the number of faces with length $i$ of the embedding is denoted by $f_i$. For instance, $f_3$ is the number of triangular faces of the embedding. Faces of length three are called \emph{triangles}, faces of length four are called \emph{quadrangular}, or \emph{rectangles}, and faces of length five are called \emph{pentagons}. For an embedding $\Pi$ of $G_n$, by $F_{\Pi}$ we denote the number of faces of $\Pi$. An easy counting shows that if $G_n$ would have an embedding with all faces being triangles, then the number of faces would be $2n3^{n-1}$, implying $\gamma(G_n) \ge 1 + \lceil 3^{n-1}(n-3)/2 \rceil$. For $n=3$ and $4$ the last inequality implies $\gamma(G_3) \ge 1$ and $\gamma(G_4) \ge 15$. To refine the lower bound, we use the fact that for each $n>1$, each edge of $G_n$ lies in precisely one triangle. Since the faces of any embedding together traverse each edge precisely twice, the total number of faces cannot be larger than it would be in the case where each edge is traversed once by a face of length 3 and once by a face of length 4. We call an embedding of $G_n$ such that every triangle bounds a face and every other face is quadrangular a \emph{triangle-quadrangular} embedding. Clearly, a triangle-quadrangular embedding may exist only if $n$ is congruent to $4 \pmod 8$ and the genus of such embedding of $G_n$ would be $1+ 3^{n-1}(5n-12)/8$. While in Theorem~\ref{thm:lb} we prove that $G_4$ does not have a triangle-quadrangular embedding, for all $n\ge 8$ with $n\equiv 4 \pmod 8$ it is an open problem whether such an embedding of $G_n$ exists. This discussion can be summarized by the following proposition and two open problems. \begin{proposition} \label{prop:genusTQ} For any $n>1$, the maximum number of faces in an embedding of $G_n$ is at most $\lfloor |E(G_n)|/3 + |E(G_n)|/4\rfloor$. Consequently $\gamma(G_n) \ge 1+\lceil 3^{n-1}(5n-12)/8\rceil$. Furthermore, $\gamma(G_n) = 1+ 3^{n-1}(5n-12)/8$ if and only if $G_n$ has a triangle-quadrangular embedding. \hfill \stvorcek \end{proposition} For $n=3,4$, and $5$, Proposition \ref{prop:genusTQ} gives $\gamma(G_3) \ge 5$, $\gamma(G_4)\ge 28$, and $\gamma(G_5)\ge 133$. Currently, Proposition \ref{prop:genusTQ} gives the best known lower bound on the genus of $G_n$ for every $n > 4$. \begin{problem} Determine all integers $n$ such that $G_n$ has a triangle-quadrangular embedding. In particular, is there an integer $n>1$ such that $G_n$ has a triangle-quadrangular embedding? \end{problem} Of a certain interest might be also quadrangular embeddings of $G_n$, that is, embeddings in which every face has length $4$. Note that the well-known genus embedding of $G_2$ in the torus is quadrangular. \begin{problem} Is there an integer $n>2$ such that $G_n$ has a quadrangular embedding? \end{problem} Our main result concerning lower bounds is Theorem \ref{thm:lb} below, which asserts that $\gamma(G_4) \ge 30$. The proof is based on a method used by Brin and Squier in \cite{BS} to prove that $\gamma(G_3) \ge 6$. While the analysis used in \cite{BS} to prove that $\gamma(G_3)\ge 7$ is quite involved, its use may lead to a better lower bound on the genus of $G_4$. We start with necessary definitions. A \emph{plane} is a subgraph of $G_n$ obtained from $G_n$ by fixing all but two coordinates. Clearly, a plane is isomorphic to $G_2$ and therefore every plane contains $9$ vertices and $18$ edges. It is easy to see that any face of length $3$ or $4$ in any embedding of $G_n$ lies in some plane of $G_n$. A cycle of $G$ is called \emph{present} if it bounds a face, otherwise it is called \emph{absent}. For a fixed embedding of $G_n$, let $a$ denote the total number of absent triangles, that is $a = T(G_n) - f_3$. Let $a_i$ denote the number of planes with precisely $i$ absent triangles. The following two results can be proved by an easy counting. \begin{proposition} \label{thm:a} Every triangle of $G_n$ lies in $n-1$ planes of $G_n$. In particular, $(n-1)a = \sum_{i=0}^6 ia_i$. %\hfill $\square$ \end{proposition} \begin{proposition} \label{thm:b} The graph $G_n$ contains precisely $\binom{n}{2}\cdot 3^{n-2}$ planes. %\hfill $\square$ \end{proposition} The following result is Proposition $3$ in \cite{BS}. \begin{lemma} \label{thm:mi} Let $P$ be a plane of $G_n$ for some $n\ge 3$. If $P$ has $i$ absent triangles, then it has at most $m_i$ present rectangles, where the values of $m_i$ are in Table \ref{fig:mi}. %\hfill $\square$ \end{lemma} \begin{table}[!htb] \begin{center} \begin{tabular}{|llllllll|} \hline $i$ & 0& 1 & 2 & 3 & 4 & 5 & 6 \\ \hline $m_i$ & 1 & 2 & 2 & 3 & 4 & 5 & 6 \\ \hline \end{tabular} \caption{The values of $m_i$. \label{fig:mi}} \end{center} \end{table} \begin{proposition} \label{prop:no-tq-G4} The graph $G_4$ does not have a triangle-quadrangular embedding. \end{proposition} \begin{proof} First note that every rectangle lies in precisely one plane of $G_n$. Suppose that $\Pi$ is a triangle-quadrangular embedding of $G_4$, in which case $\Pi$ has 81 rectangles. As all triangles are present in $\Pi$, by Lemma \ref{thm:mi} every plane has at most one present rectangle. By Proposition \ref{thm:b} the embedding contains at most $54$ rectangles, which is a contradiction. \end{proof} A calculation analogous to the proof of Proposition \ref{prop:no-tq-G4} does not exclude the possible existence of a triangle-quadrangular embedding of $G_n$ for any $n\ge 8$ with $n\equiv 4 \pmod 8$. It was observed in \cite[Proposition 2]{BS} that minimum-genus embeddings of $G_n$ with the maximum number of present triangles do not contain faces of length $5$. The next proposition is a slight extension of this result. \begin{proposition} \label{prop:no-f5} For any integer $g$ such that $g \ge \gamma(G_n)$ there is an embedding of $G_n$ in an orientable surface of genus at most $g$ without faces of length $5$. \end{proposition} \begin{proof} Let $g' = \min\{g, \gamma_M(G)\}$, where $\gamma_M(G)$ is the maximum genus of $G$. Let $\Pi$ be any embedding of $G_n$ in the orientable surface of genus $g'$; by Interpolation theorem for orientable surfaces (see \cite{duke:1966}) and the choice of $g'$ such an embedding exists. If $f_5=0$, then there is nothing to prove. Suppose that $f_5 > 0$ and that $F$ is a face of length $5$. It is easy to see that any pentagon has the form $aabab^{-1}$ for some generators $a$ and $b$ of $G_n$ ; denote by $v$ the vertex of $F$ incident with two occurrences of $a$. It follows that $\Pi$ does not contain the triangle $T$ of the form $aaa$ incident with $v$. Let $e$ be the edge of $T$ not contained in $F$. Moving $e$ into the interior of $F$ splits $F$ into a triangular face bounded by $T$ and a rectangle; denote the resulting embedding by $\Pi'$. Since the move of $e$ can be replaced by removing $e$ from $\Pi$ and then adding it back in a different position and a removal of an edge changes the number of faces by at most one, the genus of $\Pi'$ is not larger than the genus of $\Pi$. If the genera of $\Pi$ and $\Pi'$ are equal, then $e$ lies on the boundary of two distinct faces of $\Pi$. The removal of $e$ merges these two faces into a pentagon in $\Pi'$ if and only if one of them is triangle and the other is rectangle in $\Pi$. Observe that $e$ lies in precisely one triangle, the triangle $T$, which is absent in $\Pi$. Therefore, $e$ does not lie in a face of length $3$ in $\Pi$ and the removal of $e$ cannot merge two faces into a pentagon. It follows that $\Pi'$ has either a smaller genus or a smaller number of pentagons than $\Pi$ and repeating the process yields the desired embedding of $G_n$. \end{proof} \begin{theorem} \label{thm:lb} The genus of $G_4$ is at least $30$. \end{theorem} \begin{proof} Let $\Pi$ be an embedding of $G_4$. Since the union of face boundaries includes every edge precisely twice and every face that is not triangular has length at least four, we have \begin{equation} \label{eq:7} 648 = 2|E(G_4)| = \sum_{i=0}^{\infty} if_i \ge 3f_3 + 4(F_{\Pi} - f_3). \end{equation} Let $\chi$ denote the Euler characteristic of the underlying surface. Euler formula implies $F_{\Pi} = \chi + |E(G_4)| - |V(G_4)|$. Substituting the last equality into (\ref{eq:7}) and manipulating we get \begin{eqnarray} 648 &\ge& 3f_3 + 4(F_{\Pi} - f_3) \notag \\ f_3 &\ge& 4F_{\Pi} - 648 = 4\chi + 4|E(G_4)| - 4|V(G_4)| - 648 \notag \\ &=& 4\chi + 4\cdot 324 - 4\cdot 81 - 648 = 4\chi + 324. \notag \end{eqnarray} Consequently, \begin{equation} \label{eq:9} f_3 \ge 4\chi + 324. \end{equation} By Proposition \ref{prop:no-f5} we can assume that $f_5 = 0$. It follows that \begin{equation} 648 = 2|E(G_4)| = \sum_{i=0}^{\infty} if_i \ge 3f_3 + 4f_4 + 6(F_{\Pi} - (f_3+f_4)). \notag \end{equation} and after manipulation we get \begin{equation} \label{eq:10} 3f_3 + 2f_4 \ge 6\chi + 810. \end{equation} Lemma \ref{thm:mi} implies \begin{equation} \label{eq:ai} f_4 \le \sum_{i=0}^{6} m_ia_i = a_0 + a_1 + \sum_{i=0}^{6} ia_i. \end{equation} Using Proposition \ref{thm:a} for $n=4$ on $(\ref{eq:ai})$ we obtain \begin{equation} \label{eq:a} f_4 \le a_0 + a_1 +3a. \end{equation} Note that for any $n$ we have $a = T(G_n) - f_3$, substituting this equality into (\ref{eq:a}) yields $$ 3f_3 + f_4 \le a_0 + a_1 + 3\cdot 108. $$ Combining the last inequality with Proposition \ref{thm:b} for $n=4$ we get \begin{equation} \label{eq:14} 3f_3 + f_4 \le 54 + 3\cdot 108. \end{equation} Two times (\ref{eq:14}) gives an upper bound on $6f_3 + 2f_4$, while adding three times (\ref{eq:9}) to (\ref{eq:10}) bounds $6f_3 + 2f_4$ from below. Combining these inequalities gives \begin{eqnarray} 18\chi + 810 + 3\cdot 324 &\le& 2\cdot(54 + 3\cdot 108) \notag \\ 18\chi &\le& -1026 \notag \\ \chi &\le& -57. \notag \end{eqnarray} Relating $\chi \le -57$ with the genus of $G_4$ gives $\gamma(G_4) \ge 30$. \end{proof} Using the method from the proof of Theorem \ref{thm:lb} for bounding the genus of $G_5$ gives $\gamma(G_5) \ge 133$, which is the same as the bound from Proposition \ref{prop:genusTQ}. \section{Upper bounds} \label{section:upper-bounds} In this section we tackle upper bounds on the genus of $G_n$ using three different techniques. In general, the determination of the genus of $G_n$ seems to be a very difficult problem. Rather surprisingly, when we concentrate only on symmetric embeddings of $G_n$, it is possible to determine not only the symmetric genus, but also the complete set of genera of surfaces upon which $G_n$ admits a symmetric embedding. This fact is our motivation for discussing, in Subsection~\ref{subsection:symmetric}, several natural variants of genus range for groups and Cayley graphs which were not investigated before. In Subsection~\ref{subsection:computational} we present results of our computational search for low-genus embeddings of $G_4$ and discuss several related problems. Finally, Subsection~\ref{subsection:recursive} contains a recursive construction of a low-genus embedding of $G_{n+1}$ from an embedding of $G_n$ using voltage graphs. \subsection{Genus range and symmetric genus range of groups and Cayley graphs} \label{subsection:symmetric} We start by defining symmetric and strongly symmetric embedding of a Cayley graph. We follow \cite[Chapter 11]{topics} to call an embedding of a Cayley graph $G$ of a group $\Gamma$ \emph{symmetric} if the natural action of $\Gamma$ by left-multiplication on the vertices of $G$ can be extended to an action on the underlying surface. An embedding of a Cayley graph is called \emph{strongly symmetric} if it is symmetric and the extended action preserves orientation of the surface. We introduce the \emph{symmetric genus range of a Cayley graph $G$} as the set of genera of surfaces upon which $G$ admits a symmetric embedding and \emph{strong symmetric genus range of $G$} as the set of all genera of surfaces upon which $G$ has a strong symmetric embedding. Note that the symmetric genus range and strong symmetric genus range parameters are analogous to the genus range parameter, thus extending the correspondence between symmetric and all embeddings beyond the well-known (strong) symmetric genus of a Cayley graph. Our main result in this subsection is Theorem \ref{thm:strong-sym-gen-range} that completely determines strong symmetric genus range and symmetric genus range of $G_n$. A particular consequence of the theorem is that, unlike the genus range, the (strong) symmetric genus range can contain arbitrarily large gaps. For a set $X$ of elements of a group, denote by $\widetilde{X}$ the union of elements of $X$ and their inverses. Recall that a Cayley map of a Cayley graph $G$ with a generating set $X$ is an embedding of $G$ in which all local rotations induce the same cyclic order of $\widetilde{X}$. The proof of Theorem \ref{thm:strong-sym-gen-range} is based on the following correspondence between Cayley maps and symmetric embeddings. An embedding of a Cayley graph $G$ is strongly symmetric if and only if it is a Cayley map of $G$. An embedding of a Cayley graph of a group $\Gamma$ with generating set $X$ is symmetric, but not strongly symmetric, if and only if there is an index-two subgroup $\Gamma'$ of $\Gamma$ such that the local rotations of all vertices corresponding to $\Gamma'$ induce the same cyclic order of $\widetilde{X}$ and the local rotations of all vertices corresponding to $\Gamma - \Gamma'$ induce the reverse cyclic order. For more details about this correspondence see Chapters 10 (Theorem 4.1) and 11 of \cite{topics}. We conclude that the problem of determining the strong symmetric genus range of $G_n$ is equivalent with the problem of determining the genera of all Cayley maps of $G_n$. Moreover, if $\Gamma$ does not have an index-two subgroup, then every symmetric embedding of $G$ is strongly symmetric. Consequently, the fact that $Z_3^n$ does not have an index-two subgroup for any nonnegative integer $n$ implies that symmetric genus range and strong symmetric genus range of $G_n$ coincide. Recall that a generating set $X$ of a group $\Gamma$ is \emph{irredundant} if no proper subset of $X$ generates $\Gamma$. We call a Cayley graph \emph{irredundant} if it is generated by an irredundant generating set of the group. Let $B_n$ denote the bouquet of $n$ circles; that is, a single vertex incident with $n$ loops. It is well known that every Cayley graph of a group $\Gamma$ with generating set not containing involutions is the derived graph of $B_n$ for some integer $n$ and a (regular) voltage assignment in $\Gamma$, see \cite{GT}. The derived embedding is a Cayley map and each Cayley map of the graph arises as the derived embedding of an embedding of $B_n$ and some voltage assignment. The genera of the derived embeddings were determined by \cite{BW}. In the case of irredundant Cayley graphs of $Z_p^n$, the genus is given by formula \begin{equation} \label{eq:CM} \gamma(\Pi') = 1 + \frac{|Z_p^n|}{2}\left(n-1-\sum_{i=1}^t\frac{1}{m_i}\right), \end{equation} where $t$ is the number of faces of $\Pi$ and $m_i$, the \emph{period} of the $i$-th face of $\Pi$, is the group order of the sum of group elements (voltages) assigned to the edges on the boundary of the face. Note that all non-zero elements of the voltage group $Z_p^n$ have order $p$. Our first aim is to prove Lemma~\ref{lemma-period}, which characterises the possible periods of an embedding of $B_n$ with voltages in $Z_p^n$ such that the derived graph is an irredundant Cayley graph of $Z_p^n$. To this end, we need the following proposition asserting that each face of an arbitrary embedding with at least two faces traverses some edge only once. \begin{proposition} \label{prop:edge-once} Let $\Pi$ be an embedding of a connected graph. If $\Pi$ has at least two faces, then for each face $F$ of $\Pi$ there is an edge that is traversed precisely once by $F$. \end{proposition} \begin{proof} Assume that $F$ is a face of an embedding $\Pi$ and that there is no edge traversed by $F$ exactly once. Since altogether the faces of $\Pi$ traverse each edge precisely twice, it follows that each edge on the boundary of $F$ is traversed twice by $F$. Let $v$ be a vertex on the boundary of $F$. First observe that if $e$ is an edge incident with $v$ such that $e$ is traversed twice by $F$, then $F$ must traverse both the edge preceding $e$ and the edge following $e$ in the rotation at $v$. Since $F$ traverses each edge on its boundary twice, an easy inductive argument shows that $F$ traverses all edges incident with $v$. Consequently, the vertex $v$ does not lie on a boundary of any other face. The fact that the choice of $v$ was arbitrary implies that the vertices on the boundary of $F$ form a connected component of the graph and in particular, $F$ is the only face of $\Pi$. \end{proof} \begin{lemma} \label{lemma-period} Let $\Pi$ be an embedding of $B_n$ with a voltage assignment from $Z_p^n$ such that the derived graph is an irredundant Cayley graph of $Z_p^n$, where $p$ is an odd prime and $n$ is a positive integer If $\Pi$ has one face, then the period of the face is $1$. If $\Pi$ has at least two faces, then the period of each face of $\Pi$ is $p$. \end{lemma} \begin{proof} Since the generating set is irredundant, the order of every voltage is strictly greater than $1$ and the voltages are pairwise independent. As the order of every element of $Z_p^n$ is $p$, it follows that the order of every voltage is exactly $p$. Clearly, if $\Pi$ has precisely one face, then every edge is traversed twice by the face, once in each direction, implying that the period is the group identity. Assume that $\Pi$ has at least two faces. If $F$ is a face of $\Pi$, then the boundary of $F$ contains an edge $e$ that is traversed precisely once by $F$ by Proposition~\ref{prop:edge-once}. The voltage assigned to $e$ has order $p$ and is independent from all other voltages assigned to the edges of $F$, thus the period of $F$ is at least $p$. The fact that $Z_p^n$ does not contain elements of order strictly greater than $p$ implies that the period of $F$ is exactly $p$. \end{proof} \begin{theorem} \label{thm:strong-sym-gen-range} Let $G$ be an irredundant Cayley graph of $Z_p^n$ for some odd prime $p$ and a positive integer $n$. Then the symmetric genus range and the strong symmetric genus range of $G$ coincide and are given by $$\{1+p^{n-1}[(n-1)(p-1)-2]/2 + gp^{n-1}; g \mathrm{\ is\ an\ integer\ such\ that\ } 0\le g < \lfloor n/2 \rfloor\}$$ $$ \cup\ \ \{ 1+p^n(n-2)/2; \mathrm{if}\ n \ \mathrm{is\ even} \}. $$ \end{theorem} \begin{proof} It is not difficult to see that any Cayley map of $G$ is the derived embedding of an embedding of $B_n$ with voltages from $Z_p^n$ (see \cite[Section 6.2.1]{GT}). Clearly, $B_n$ is a planar graph, the maximum genus of $B_n$ is $\lfloor n/2 \rfloor$, and Interpolation theorem for orientable surfaces implies that $B_n$ has a cellular embedding in the orientable surface of genus $g$ if and only if $0\le g\le \lfloor n/2 \rfloor$. Assume that an embedding $\Pi$ of $B_n$ has at least two faces. By Lemma \ref{lemma-period} the period of each face is $p$ and therefore the genus of the derived embedding is determined by the number of faces of the base embedding alone. To calculate the genus of the derived embedding $\Pi'$, we can substitute $f/p$ for the sum in $(\ref{eq:CM})$, where $f$ is the number of faces of $\Pi$. Additionally, expressing $f$ from the Euler formula for $\Pi$ we get $f = n+1 -2g$ and again substituting gives $\gamma(\Pi') = 1+p^{n-1}[(n-1)(p-1) -2 + 2g)]/2$. A straightforward calculation shows that if the embedding of $B_n$ has one face (and necessarily $n$ is even), then the genus of the derived embedding is $1+ p^n(n-2)/2$. \end{proof} The lowest genus of Cayley maps of $G_n$ calculated in Theorem~\ref{thm:strong-sym-gen-range} gives the following upper bound on $\gamma(G_n)$. \begin{theorem} \label{lemma:genusCM} \label{thm:CM} Let $n$ be a nonnegative integer. Then $\gamma(G_n) \le 1+3^{n-1}(n-2)$. %\hfill $\square$ \end{theorem} For $n=3,4$, and $5$, Theorem \ref{lemma:genusCM} gives $\gamma(G_3) \le 10$, $\gamma(G_4) \le 55$, and $\gamma(G_5) \le 244$. %\medskip Concerning the genera of (strong) symmetric embeddings of Cayley graphs, a large part of the existing results deal with determination of the genus -- the minimum integer in the symmetric genus range. For symmetric genus, the focus is usually on a specific group or a family of groups, or a specific surface, see for example \cite{conder:1985} and \cite{MZ:2003}. Another important direction in the study of symmetric embeddings of Cayley graphs is aimed at regular maps arising from Cayley graphs, see for example \cite{RSJTW}. The following problem offers a slightly different perspective on symmetric embeddings of Cayley graphs. Theorem \ref{thm:strong-sym-gen-range} indicates that this problem may be approachable in the case of irredundant Cayley graphs of groups with relatively simple structure such as $Z_p^n$. \begin{problem} For a given Cayley graph $G$, determine the symmetric genus range and the strong symmetric genus range of $G$. \end{problem} The \emph{genus range} of a graph $G$ is the set of integers $g$ such that $G$ admits a cellular embedding in the orientable surface of genus $g$; the largest integer in the genus range of $G$ is called the \emph{maximum genus} of $G$ and it is denoted by $\gamma_M(G)$. By the Interpolation theorem for orientable surfaces (\cite{duke:1966}), an integer $g$ lies in the genus range of $G$ if and only if $\gamma(G) \le g \le \gamma_M(G)$, that is, the genus range is always a contiguous interval. On the other hand, as a consequence of Theorem~\ref{thm:strong-sym-gen-range} we get that the (strong) symmetric genus range of a Cayley graph can contain arbitrarily large gaps. \medskip The minimum genus of a group $\Gamma$ was defined in \cite{white:1972} as the minimum among genera of all Cayley graphs of $\Gamma$. For a group $\Gamma$, we introduce the \emph{genus range of $\Gamma$} as the set of all integers $g$ such that there is an irredundant Cayley graph of $\Gamma$ having a cellular embedding in the orientable surface of genus $g$. Rather surprisingly, the concept of the the genus range of a group was not investigated before. Theorem \ref{thm:strong-sym-gen-range} suggests that the problem of determining the genus range of a group may have different characteristics and a more algebraic flavour when restricted to symmetric embeddings of Cayley graphs of the group. Due to this expected different behaviour, we introduce also the symmetric variants of the genus range of a group. The \emph{(strong) symmetric genus range of $\Gamma$} is the set of integers $g$ such that there is a Cayley graph for $\Gamma$ having a (strong) symmetric cellular embedding in the orientable surface of genus $g$, where we may or may not require the Cayley graphs to be irredundant. Nonorientable variants of the genus range parameters of a group may be introduced analogously. The restriction to irredundant generating sets in the calculations of the genus of a group is justified by the following observation: if $X$ and $X'$ are generating sets of a group $\Gamma$ such that $X \subseteq X'$, then the Cayley graph $G$ of $\Gamma$ generated by $X$ is a subgraph of the Cayley graph $G'$ generated by $X'$ and thus $\gamma(G) \le \gamma(G')$. Let $\gamma_M(\Gamma)$ denote the the maximum integer in the genus range of a group $\Gamma$; we say that $\gamma_M(\Gamma)$ is the \emph{maximum genus of} $\Gamma$. While the value of the minimum genus of a group does not depend on the precise definition of the arising Cayley graphs, the value of maximum genus can be affected by the treatment of the involutions (elements of order $2$) in the generating sets. It is customary to define the (standard) \emph{Cayley graph} as having cycles of length $2$ corresponding to involutions, and to define the \emph{reduced} (or alternative) \emph{Cayley graph} in which each cycle of length two corresponding to an involution is replaced by a single edge, see for instance \cite{GT}. Recall that a graph $G$ is called \emph{upper-embeddable} if its maximum genus reaches the natural upper bound $\lfloor \beta(G)/2\rfloor$, where $\beta(G)$ is the cycle rank of $G$. Equivalently, $G$ is upper-embeddable if and only if it has an embedding with one face (if its cycle rank is even), respectively with two faces (if its cycle rank is odd). Nedela and \v{S}koviera \cite{NS:1989} proved that every Cayley graph is upper-embeddable and that every reduced Cayley graph $G$ is upper-embeddable unless the generating set consists of two elements $r$ and $s$ such that $r^2 = s^3 = 1$ and $|V(G)| \ge 18$, in which case the graph is cubic and its the maximum genus equals $|V(G)|/6 + 1$ (where $|V(G)|$ is always divisible by $6$). It follows that the maximum genus of a group $\Gamma$ is essentially determined by the maximum degree of a Cayley graph of $\Gamma$, that is, it reduces to a question about generating sets of $\Gamma$. If we would not require the Cayley graphs to be irredundant, then all elements of $\Gamma$ could be taken as a generating set, yielding a graph with the maximum genus among all Cayley graphs of $\Gamma$, rendering the problem trivial. Since we consider irredundant Cayley graphs, we cannot take $\Gamma$ as the generating set and the determination of the maximum genus of a group $\Gamma$ splits into two cases according to the treatment of involutions. (Note that the degree, and hence also the maximum genus, of the Cayley graph generated by $\Gamma$ also depends on whether we consider standard or alternative Cayley graphs.) For standard Cayley graphs, establishing the maximum genus of $\Gamma$ is equivalent with finding an irredundant generating set of $\Gamma$ with the maximum number of elements. For alternative Cayley graphs, establishing the maximum genus of $\Gamma$ is equivalent with determining a generating set $X$ of $\Gamma$ such that $2|X| - i_X$ is maximized, where $i_X$ is the number of involutions in $X$. In this context it might be interesting to know all groups $\Gamma$ whose maximum genus is attained by non-upper-embeddable Cayley graph. Since $Z_p^n$ have essentially only one irredundant generating set and do not contain involutions, we get the next results. \begin{theorem} For any odd prime $p$, the maximum genus of $Z_p^n$ is given by $$\gamma_M(Z_p^n) = \lfloor((n-1)p^n -1)/2\rfloor. $$ %\vspace*{-6mm} %\hfill $\square$ \end{theorem} \begin{theorem} For any odd prime $p$, the symmetric genus range and the strong symmetric genus range of $Z_p^n$ coincide and are given by $$\{1+p^{n-1}[(n-1)(p-1)-2]/2 + gp^{n-1}; g \mathrm{\ is\ an\ integer\ such\ that\ } 0\le g < \lfloor n/2\rfloor \}$$ $$ \cup\ \ \{ 1+p^n(n-2)/2; \mathrm{if}\ n \ \mathrm{is\ even} \}. $$ %\vspace*{-4mm} %\hfill $\square$ \end{theorem} It follows that the genus range of $Z_3$, $Z_3^2$, and $Z_3^3$ is equal to $\{0\}$, $\{1,2,3,4\}$, and $\{7,\ldots, 26\}$, respectively. The definition of genus range of a group leads to the following problem. \begin{problem} For a given group $\Gamma$, determine the genus range and the (strong) symmetric genus range of~$\Gamma$. \end{problem} In spite of the Interpolation theorem for orientable surfaces and Theorem \ref{thm:strong-sym-gen-range}, it is natural to ask whether the genus range and the (strong) symmetric genus range of a group can contain gaps. Finally, note that while the case of $G_n$ is probably among the most difficult in determining the (non-symmetric) genus among the Cayley graphs of abelian groups, most likely it is one of the easiest for the (strong) symmetric genus. \subsection{Computer search} \label{subsection:computational} The first author wrote a series of computer programs for experimenting with the embeddings of $G_n$. The second author wrote an independent program for checking the validity of results. The data are available at the E-JC webpage accompanying the paper and this section briefly summarizes the main results. We start by introducing the invariant used to distinguish nonisomorphic embeddings of a graph. A \emph{face distribution} of an embedding $\Pi$ is the sequence $\{f_i\}$, where $f_i$ is the number of faces of $\Pi$ with length $i$. The concept of face distribution appears as region distribution in \cite{white:2001}, where all possible face distributions of $K_5$ are presented. A face of an embedding is called \emph{repetitive} if it contain some vertex more than once. An \emph{extended face distribution} of an embedding $\Pi$ is the face distribution of $\Pi$ together with the sequence $\{r_i\}$, where $r_i$ is the number of repetitive faces of length $i$. Clearly, if two embeddings of the same graph have different extended face distribution, then they are nonisomorphic. \begin{theorem} \label{thm:CS} For the genus of $G_4$ we have $\gamma(G_4) \le 37$. Moreover, there are more than $10\thinspace 000$ nonisomorphic embeddings of $G_4$ into the orientable surface of genus $37$ with pairwise distinct extended face distributions. %\hfill $\square$ \end{theorem} An embedding of $G_4$ in the orientable surface of genus $37$ was obtained by computer search; the extended face distribution of the embedding is presented in Table \ref{fig:G4-face-distribution}. The rotation schemes for more than $10\thinspace 000$ nonisomorphic embeddings of $G_4$ in the orientable surface of genus $37$ and their extended face distributions can be found on the web pages containing the supplementary material. For the sake of completeness we present the rotation scheme of one such embedding in Table~\ref{fig:G4_scheme} and the extended face distribution of the embedding in Table~\ref{fig:G4-face-distribution}. \begin{table}[htb] \begin{center} \begin{tiny} \begin{tabular}{l} 0000: 0200, 0100, 0001, 0002, 0020, 1000, 2000, 0010\\ 1000: 1010, 1020, 1200, 1100, 2000, 0000, 1002, 1001\\ 2000: 1000, 2100, 2200, 2002, 2001, 2020, 2010, 0000\\ 0100: 0110, 0120, 1100, 0102, 0101, 0000, 0200, 2100\\ 1100: 1102, 2100, 1000, 1200, 0100, 1120, 1110, 1101\\ 2100: 2120, 2110, 0100, 2200, 2000, 1100, 2102, 2101\\ 0200: 0000, 0210, 0220, 0202, 0201, 1200, 2200, 0100\\ 1200: 1201, 1202, 1100, 1000, 1220, 1210, 2200, 0200\\ 2200: 2000, 2100, 0200, 1200, 2210, 2201, 2202, 2220\\ 0010: 0011, 0110, 0210, 0000, 2010, 1010, 0020, 0012\\ 1010: 1000, 1012, 1020, 0010, 2010, 1011, 1210, 1110\\ 2010: 2012, 2011, 1010, 0010, 2000, 2020, 2110, 2210\\ 0110: 0010, 0112, 0111, 0120, 0100, 2110, 1110, 0210\\ 1110: 2110, 1111, 1100, 1120, 1112, 1010, 1210, 0110\\ 2110: 2112, 2111, 1110, 0110, 2100, 2120, 2210, 2010\\ 0210: 0200, 0010, 0110, 1210, 0212, 0211, 2210, 0220\\ 1210: 1211, 2210, 1200, 1220, 1212, 0210, 1110, 1010\\ 2210: 2211, 2212, 2010, 2110, 0210, 2220, 2200, 1210\\ 0020: 0220, 0120, 0010, 1020, 2020, 0000, 0022, 0021\\ 1020: 1022, 1021, 1120, 1220, 1000, 2020, 0020, 1010\\ 2020: 2220, 2120, 0020, 1020, 2010, 2000, 2021, 2022\\ 0120: 0110, 0121, 0122, 0020, 0220, 2120, 1120, 0100\\ 1120: 0120, 2120, 1220, 1020, 1121, 1122, 1110, 1100\\ 2120: 2121, 2122, 2020, 2220, 1120, 0120, 2110, 2100\\ 0220: 0020, 2220, 1220, 0221, 0222, 0200, 0210, 0120\\ 1220: 1222, 1210, 1200, 1020, 1120, 2220, 0220, 1221\\ 2220: 0220, 1220, 2120, 2020, 2200, 2222, 2221, 2210\\ 0001: 0201, 0021, 0011, 2001, 1001, 0002, 0000, 0101\\ 1001: 1000, 1002, 0001, 2001, 1201, 1101, 1021, 1011\\ 2001: 2201, 1001, 0001, 2011, 2021, 2000, 2002, 2101\\ 0101: 1101, 0201, 0001, 0100, 0102, 0121, 0111, 2101\\ 1101: 2101, 1102, 1100, 1111, 1121, 1001, 1201, 0101\\ 2101: 2100, 2102, 2201, 2001, 1101, 0101, 2111, 2121\\ 0201: 2201, 0211, 0221, 0001, 0101, 1201, 0200, 0202\\ 1201: 1101, 1001, 2201, 1202, 1221, 1211, 1200, 0201\\ 2201: 0201, 1201, 2001, 2101, 2202, 2200, 2221, 2211\\ 0011: 2011, 0001, 0021, 0111, 0211, 0010, 0012, 1011\\ 1011: 0011, 1012, 1001, 1021, 1111, 1211, 1010, 2011\\ 2011: 2021, 2001, 0011, 1011, 2010, 2012, 2111, 2211\\ 0111: 0121, 0110, 0112, 1111, 2111, 0101, 0211, 0011\\ 1111: 1112, 1211, 1011, 1121, 1101, 1110, 2111, 0111\\ \end{tabular} \begin{tabular}{l} 2111: 2112, 2211, 2011, 2121, 2101, 0111, 1111, 2110\\ 0211: 1211, 0210, 0212, 0011, 0111, 0221, 0201, 2211\\ 1211: 2211, 1210, 1011, 1111, 1212, 1201, 1221, 0211\\ 2211: 2011, 2111, 2212, 2210, 1211, 0211, 2201, 2221\\ 0021: 0011, 0001, 0221, 0020, 0022, 2021, 1021, 0121\\ 1021: 0021, 2021, 1121, 1020, 1022, 1221, 1011, 1001\\ 2021: 2020, 2001, 2011, 2221, 2121, 1021, 0021, 2022\\ 0121: 0101, 0122, 0120, 0111, 0021, 1121, 2121, 0221\\ 1121: 1021, 2121, 0121, 1101, 1111, 1221, 1122, 1120\\ 2121: 2120, 2101, 0121, 1121, 2021, 2221, 2111, 2122\\ 0221: 0222, 0220, 0021, 0201, 0211, 0121, 2221, 1221\\ 1221: 2221, 1222, 1121, 1021, 1220, 1211, 1201, 0221\\ 2221: 2220, 2222, 1221, 0221, 2121, 2021, 2211, 2201\\ 0002: 0000, 0001, 1002, 2002, 0012, 0102, 0202, 0022\\ 1002: 0002, 1001, 1000, 1022, 1012, 1102, 1202, 2002\\ 2002: 2022, 2012, 0002, 1002, 2202, 2102, 2001, 2000\\ 0102: 2102, 0202, 0002, 0112, 0122, 0101, 0100, 1102\\ 1102: 1202, 1002, 1112, 1122, 1100, 1101, 2102, 0102\\ 2102: 2202, 2101, 2100, 2122, 2112, 0102, 1102, 2002\\ 0202: 1202, 0201, 0200, 0222, 0002, 0102, 0212, 2202\\ 1202: 1002, 1102, 1200, 1212, 1222, 1201, 0202, 2202\\ 2202: 2200, 2201, 2102, 2002, 1202, 0202, 2212, 2222\\ 0012: 1012, 0011, 0010, 0022, 0212, 0112, 0002, 2012\\ 1012: 0012, 2012, 1212, 1112, 1002, 1022, 1010, 1011\\ 2012: 0012, 2002, 2022, 2112, 2011, 2010, 2212, 1012\\ 0112: 0012, 0212, 2112, 1112, 0111, 0110, 0122, 0102\\ 1112: 1102, 1012, 1212, 1111, 0112, 2112, 1110, 1122\\ 2112: 2012, 2212, 2111, 2110, 1112, 0112, 2102, 2122\\ 0212: 0012, 0222, 0211, 0210, 1212, 2212, 0202, 0112\\ 1212: 1211, 1112, 1012, 2212, 0212, 1210, 1222, 1202\\ 2212: 1212, 2012, 2210, 2211, 2112, 2222, 2202, 0212\\ 0022: 1022, 2022, 0021, 0020, 0002, 0222, 0012, 0122\\ 1022: 1012, 1002, 2022, 0022, 1122, 1222, 1021, 1020\\ 2022: 0022, 1022, 2122, 2222, 2012, 2002, 2020, 2021\\ 0122: 0222, 2122, 1122, 0022, 0120, 0121, 0102, 0112\\ 1122: 1112, 1120, 1121, 1222, 1022, 0122, 2122, 1102\\ 2122: 2120, 2121, 2112, 2102, 1122, 0122, 2222, 2022\\ 0222: 0212, 0022, 0202, 0220, 0221, 1222, 2222, 0122\\ 1222: 2222, 0222, 1202, 1212, 1220, 1022, 1122, 1221\\ 2222: 0222, 1222, 2221, 2220, 2202, 2212, 2022, 2122\\ \end{tabular} \end{tiny} \end{center} \caption{Rotation scheme for an embedding of $G_4$ with genus $37$.} \label{fig:G4_scheme} \end{table} \begin{table}[htb] \begin{center} \begin{tabular}{|l|ccccccc|} \hline length of the face & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ \hline number of faces & 88 & 59 & 8 & 10 & 2 & 2 & 2\\ \hline number of repetitive faces & 0 & 0 & 0 & 0 &2 & 0 & 0\\ \hline \end{tabular} \end{center} \caption{Extended face distribution of an embedding of $G_4$ with genus $37$ presented in Table \ref{fig:G4_scheme}.} \label{fig:G4-face-distribution} \end{table} The problem of determining the complete genus distribution of a graph $G$ asks for the number of embeddings of $G$ in every surface, where two embeddings are considered to be different if their rotation schemes differ. Therefore, the following theorem does not take into account any symmetries of $G_2$ or the embedding. \begin{theorem} The embedding range of $G_2$ is $[1,5]$, that is, $G_2$ admits a cellular embedding into the surfaces of genus $1, 2, 3, 4$, and $5$, and the complete genus distribution of $G_2$ is given in Table \ref{fig:genus_distribution}. In particular, there are $330$ genus embeddings into torus with only $7$ distinct extended face distributions, presented in Table \ref{table:G2-distinct}, and $46\,908$ embeddings in the double torus with $146$ distinct extended face distribution. %\hfill $\square$ \end{theorem} \begin{table}[htb] \begin{center} \begin{tabular}{|r|ccccccc|} \hline genus & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline $\sharp$ embeddings & 0 & 330 & 46\,908 & 1\,385\,214 & 6\,516\,564 & 2\,128\,680 & 0\\ \hline \end{tabular} \end{center} \caption{Complete genus distribution of $G_2$.} \label{fig:genus_distribution} \end{table} On the web pages containing the supplementary material we list the rotations schemes and extended face distributions of all embeddings of $G_2$ with genus at most two. Furthermore, to indicate the rate of growth of the number of non-isomorphic low-genus embeddings of $G_n$, we provide also all distinct face distributions and the corresponding rotation schemes for embeddings of $G_2$ with genus at most two. Perhaps surprisingly, $G_2$ embedded in the torus admits only $7$ distinct extended face distributions, they are listed in Table \ref{table:G2-distinct} along with the number of such embeddings. Three of these distributions contain exactly one repetitive face and four of them do not contain a repetitive face. Finally, note that the two embeddings with $9$ quadrangles are mirror images of each other. \begin{table}[htb] \begin{center} \begin{tabular}{|c|cccc||c|c|} \hline length of the face & 3 & 4 & 5 & 6 & length of the repetitive face & frequency\\ \hline \hline number of faces & 6 & 2 & 0 & 0 & 10 & 36\\ \hline number of faces & 5 & 2 & 1 & 0 & 8 & 144\\ \hline number of faces & 4 & 2 & 2 & 1 & 6 & 72\\ \hline number of faces & 4 & 3 & 0 & 2 & -- & 36\\ \hline number of faces & 4 & 1 & 4 & 0 & -- & 36\\ \hline number of faces & 6 & 0 & 0 & 3 & -- & 4\\ \hline number of faces & 0 & 9 & 0 & 0 & -- & 2 \\ \hline \end{tabular} \end{center} \caption{All distinct extended face distributions of $G_2$ embedded in the torus.} \label{table:G2-distinct} \end{table} Moving from $G_2$ to $G_3$, we observe that the number of genus embeddings with pairwise distinct extended face distributions grows rapidly, as evidenced by the following theorem. Although at present we do not know whether 37 is the actual value of $\gamma(G_4)$, the change between $G_2$ and $G_3$ indicates that the actual number of genus embeddings with pairwise distinct extended face distributions of $G_4$ may be significantly larger than the number $10\thinspace 000$ presented in Theorem~\ref{thm:CS}. \begin{theorem} \label{thm:G3} There are at least $1319$ genus embeddings of $G_3$ with pairwise distinct extended face distributions. %\hfill $\square$ \end{theorem} The rotation schemes of the nonisomorphic genus embeddings of $G_3$ from Theorem~\ref{thm:G3} can be found on the web pages containing the supplementary material. Table \ref{table:G3-selected} contains several particularly interesting face distributions of genus embeddings of $G_3$; the corresponding embeddings can be also found as a separate part of the supplementary material. Although all these embeddings have all faces nonrepetitive, it is interesting that for all of them except the first two, there is also an embedding with the same face distribution and one of the longest faces repetitive. Note also that the last embedding in Table \ref{table:G3-selected} has the same face distribution as the embedding constructed in \cite{MPSW} to show that $\gamma(G_3)\le 7$. \begin{table}[htb] \begin{center} \begin{tabular}{|c|cccc||c|} \hline length of the face & 3 & 4 & 5 & 6 & length of the remaining face\\ \hline \hline number of faces & 22 & 12 & 0 & 8 & --\\ \hline number of faces & 24 & 7 & 4 & 7 & --\\ \hline number of faces & 24 & 9 & 0 & 9 & --\\ \hline number of faces & 26 & 9 & 0 & 6 & 12\\ \hline number of faces & 27 & 6 & 0 & 8 & 9\\ \hline number of faces & 27 & 8 & 0 & 6 & 13 \\ \hline number of faces & 27 & 9 & 0 & 5 & 15 \\ \hline \end{tabular} \end{center} \caption{Face distributions of some of the $1319$ genus embeddings of $G_3$ from Theorem \ref{thm:G3}.} \label{table:G3-selected} \end{table} In general, $G_n$ has $\prod_{v\in V(G_n)} (\mathrm{deg}(v)-1)! = [(2n-1)!]^{3^n}$ rotation schemes. In particular, $G_3$ and $G_4$ have $120^{27} \approx 10^{56}$, respectively $5040^{81} \approx 10^{299}$, rotation schemes, which makes exhaustive search infeasible even for $G_3$. \subsection{Recursive construction} \label{subsection:recursive} Let $G'_n$ denote $G_n$ with a loop attached to every vertex. Clearly, $G_{n+1}$ is the derived graph of $G'_n$ with respect to $Z_3$, where a non-zero element of $Z_3$ is assigned to an edge $e$ if and only if $e$ is a loop. The idea to obtain an embedding of $G_3$ as a lift of the quadrilateral embedding of $G_2$ appears in \cite{white:2001}. In this subsection we explore the possibilities to use lifts of $G'_n$ to bound the genus of $G_{n+1}$ in the general case. Our main result, Theorem~\ref{thm:recursive}, shows that \emph{any} minimum-genus embedding of $G_n$ can be lifted in such a way that the resulting embedding of $G_{n+1}$ has low genus. First observe that if a loop bounds a face (of length 1) and the voltage assigned to the loop has order $3$, then the face lifts to a triangle. Therefore, if every loop bounds a face and a non-zero element of $Z_3$ is assigned to every loop, then the derived embedding has at least $|V(G_n')|$ triangles. The main idea of the proof of Theorem \ref{thm:construction} is that if we can embed the loops inside faces of an embedding $\Pi$ in such a way that every face contains either zero or at least two loops, then there is a voltage assignment to loops such that every face of $\Pi$ with length at least $2$ lifts to three faces. The fact that the loops can be distributed appropriately is captured by the following definition. \begin{definition} Let $\Pi$ be an embedding of a graph $G$. A \emph{face-covered partition} of $\Pi$ is a partition of the vertex set $V(G)$ into sets $P_i$, $i=1,\ldots, k$, satisfying the following two conditions: \begin{itemize} \item[(i)] for each $i\in \{1,\ldots, k\}$, the set $P_i$ contains at least two vertices of $G$; and \item [(ii)] for each $i\in \{1,\ldots, k\}$, there is a face of $\Pi$ whose boundary contains $P_i$. % all vertices in $P_i$. \end{itemize} \end{definition} Our method does not rely on the fact that the base graph is $G_n$ and we state the result in a more general form. \begin{theorem} \label{thm:construction} Let $\Pi$ be an embedding of a graph $G$ in an orientable surface $S$. Let $G'$ denote $G$ with a loop attached to every vertex. If $\Pi$ admits a face-covered partition, then there is an embedding of $G'$ in $S$ and a voltage assignment from $Z_3$ to $G'$ such that the derived graph is $G\square K_3$ embedded with $3F_{\Pi} + |V(G)|$ faces. \end{theorem} \begin{proof} Let $\mathcal{P} = \{P_1,\ldots, P_k\}$ be a face-covered partition of $\Pi$ and let $F_i$ be a face of $\Pi$ that covers $P_i$ for $i\in \{1,\ldots, n \}$. We arbitrarily choose a preferred direction for each loop $e$ and denote it by $e$; the opposite direction is denoted by $e^{-1}$. For each vertex $v\in \mathcal{P}$, embed the loop $e$ based at $v$ into $F_i$ in such a way that the rotation at $v$ is $(ee^{-1}\ldots)$. Denote the resulting embedding by $\Pi'$. Denote by $L$ the set of loops added to $G$ and by $F_L$ the set of faces of length $1$ bounded by a loop from $L$. We say that a face $F$ of $\Pi'$ \emph{contains a loop $l$} if the boundary of $F$ traverses $l$. Our goal is to prescribe a voltage assignment $\zeta$ from the arcs of $G'$ to the elements of $Z_3$ such that the derived embedding has $3F_{\Pi} + |V(G)|$ faces. To achieve this property, we choose $\zeta$ such that the period of each face in $F_L$ is $3$ and the period of each face of $\Pi'$ not in $F_L$ is $1$. First note that any loop $e$ from $L$ lies on the boundary of two distinct faces in $\Pi'$, one of them is a face of length $1$ bounded by $e$, and the other is a face of length at least $2$. For any arc $a$ of $G$ not contained in $G'$ let $\zeta(a) = 0$. Let $F$ be a face of $\Pi'$ not in $F_L$ and containing a loop. The choice of $\mathcal{P}$ and $\Pi'$ implies that $F$ contains at least two loops. If $F$ contains two loops $e$ and $f$, let $\zeta(e) = 1$ and $\zeta(f)=2$. If $F$ contains three loops $e$, $f$, and $g$, let $\zeta(e) = \zeta(f) = \zeta(g) = 1$. Finally, if $F$ contains at least four loops, define the value of $\zeta$ for loops in $F$ as follows. Repeatedly choose two loops $e$ and $f$ which had so far not been assigned a value of $\zeta$ and let $\zeta(e) = 1$ and $\zeta(f) = 2$. This assigns the value $\zeta$ for all loops contained in $F$, and consequently for all arcs of $G'$. Now we show that the periods of all faces of $\Pi'$ under $\zeta$ have the required values. The boundary of any face of $F_L$ contains precisely one arc $a$ corresponding to a loop in $L$ and $\zeta(a) = 1$ or $\zeta(a)=2$. In both cases the period of the face in $Z_3$ is $3$. If $F$ is a face of $\Pi'$ which is not in $F_L$ and which does not contain a loop, then all arcs on the boundary of $F$ are assigned $0$ by $\zeta$ and the period of $F$ is $1$. If $F$ is a face of $\Pi'$ which is not in $F_L$ and which contains two or three loops, then clearly the period of the face is $1$. The fact that the period of $F$ is $0$ if $F$ contains at least four loops follows from a straightforward inductive argument, which is omitted. Clearly, the derived graph of $G'$ under $\zeta$ in $Z_3$ is $G\square K_3$. The embedding $\Pi'$ has $F_{\Pi} + |V(G)|$ faces, $F_{\Pi}$ of them with period $3$ and $|V(G)|$ of them with period $1$. Therefore, the derived embedding of $\Pi'$ under $\zeta$ in $Z_3$ has $F_{\Pi} + |V(G)|$ faces, which completes the proof. \end{proof} Note that in the previous theorem each new triangle of $G\square K_3$ is a face of the derived embedding and that it is possible to calculate the lengths of all faces of the derived embedding using the lengths of the faces of $\Pi$ and the face-covered partition of $G$. Moreover, the derived embedding admits a face-covered partition consisting from the new triangles of $G\square K_3$. Our next aim is a more general statement that every minimum-genus embedding of $G_n$ admits a face-covered partition. The main idea is that for any embedding and any matching, each pair of matched vertices is covered by some face. As $G_n-v$ contains a perfect matching for any vertex $v$, the problem reduces to covering the exceptional vertex $v$. To cover this vertex we then use the fact that the embedding has a face of length at most $5$. In the proofs of the following two auxiliary results we use the fact that the vertices of $G_n$ can be bijectively identified with words of length $n$ over $\{0,1,2\}$ with two vertices being adjacent if and only if their representations differ at exactly one position. \begin{lemma} \label{lemma:matchings} Let $S$ be a set of three pairwise adjacent vertices of $G_n$, where $n\ge 1$. Then $G_n-S$ has a perfect matching. Consequently, $G_n-v$ has a perfect matching for any vertex $v$. \end{lemma} \begin{proof} First observe that if $G_n -S$ has a perfect matching for each triangle $S$, then $G_n-v$ has a perfect matching for each vertex $v$ since every vertex lies in some triangle. To show that $G_n -S$ indeed has a perfect matching for each triangle $S$ we proceed by induction on $n$. For $n=1$ the claim is obvious. For $n\ge 2$ we show how to construct the desired matching. From the fact that $S$ forms a triangle it follows that there is a unique position such that the representations of the vertices of $S$ pairwise differ only in this position. Restricting $G_n-S$ to all but this one position yields three disjoint copies of $G_{n-1}$, each of them with one vertex removed. By the induction hypothesis the copies of $G_{n-1}$ have perfect matchings; the union of these perfect matchings is a perfect matching of $G_n-S$. \end{proof} \begin{proposition} \label{proposition:fcp} Let $\Pi$ be an embedding of $G_n$ that contains a face of length at most $5$. Then $\Pi$ admits a face-covered partition of $G$. \end{proposition} \begin{proof} We distinguish three cases according to the length of the shortest face of $\Pi$.\\ i) \emph{The length of a shortest face of $\Pi$ is $3$.} Let $F$ be a face of length $3$ and let $S$ be the set of vertices incident with $F$. By Lemma \ref{lemma:matchings}, there is a perfect matching $M$ of $G_n-S$. Denote the edges of $M$ by $m_1,\ldots, m_k$ and let $P_i = \{u_i, v_i\}$, where $u_i$ and $v_i$ are the endpoints of $m_i$ for $i\in \{1,\ldots, k\}$. Finally, let $P_{k+1} = S$. Since every edge $m_i$ is traversed by some face of $\Pi$, for any $i$, $1\le i\le k$, there is a face of $\Pi$ that covers both vertices of $P_i$. Moreover, the vertices of $P_{k+1}$ are covered by $F$. It follows that the system of sets $P_i$ for $i\in \{1,\ldots, k+1 \}$ is a face-covered partition of $\Pi$. \\ ii) \emph{The length of a shortest face of $\Pi$ is $4$.} Let $F$ be a face of length $4$ in $\Pi$. Without loss of generality suppose that the vertices of $F$ are represented by $00x$, $10x$, $11x$, and $01x$, where $x$ is arbitrary, but fixed word over $\{0,1,2\}$ with length $n-2$. Consider the graph $G' = G_n - \{abx; a,b\in\{0,1,2\}\}$. Restricting $G'$ to positions $2,\ldots, n$ yields three disjoint copies of $G_{n-1}$, each of them with a triangle at position $2$ removed. By Lemma \ref{lemma:matchings}, each copy of $G_{n-1}$ with a triangle removed admits a perfect matching; denote by $M$ the union of these perfect matchings. We construct a face-covered partition of $G_n$ using $M$ and a partition covering the three removed triangles. Assume that the edges of $M$ are $u_1v_1, u_2v_2,\ldots, u_kv_k$, where $k=3^{n-1}-3$. Let $P_i = \{u_i, v_i\}$ for each $i\in \{1,\ldots, k\}$. Clearly, the sets $P_i$ cover all vertices of $M$. To cover the vertices of the removed triangles, let $P_{k+1} = \{00x, 10x,11x\}$, $P_{k+2} = \{20x, 21x\}$, $P_{k+3} = \{01x, 02x\}$, and $P_{k+4} = \{12x, 22x\}$. Since the set $P_{k+1}$ is covered by the face $F$ and any set $P_i$ for $i\neq k+1$ contains exactly two vertices joined by an edge, the system of sets $P_i$, $i\in\{1,\ldots, k+4\}$ forms the desired face-covered partition. \\ iii) \emph{The length of a shortest face of $\Pi$ is $5$.} Every pentagon in $G_n$ has form $aabab^{-1}$ for some generators of $G_n$ $a$ and $b$. In particular, every pentagon contains vertices of some triangle $S$. To get the desired face-covered partition it suffices to take the face-covered partition for $\Pi$ covering the vertices of $S$ constructed in the proof of case i). \end{proof} \begin{proposition} \label{proposition:min-genus-short-faces} Every embedding of $G_n$ with genus less than $1+\lfloor 3^{n-1}(2n-3)/2\rfloor$ contains a face of length at most $5$. In particular, every minimum-genus embedding of $G_n$ contains a face of length at most $5$. \end{proposition} \begin{proof} If an embedding $\Pi$ of $G_n$ has the length of a shortest face at least $6$, then $\Pi$ contains at most $n3^{n-1}$ faces. Using Euler formula we get that the genus of $\Pi$ is at least $1+\lceil 3^{n-1}(2n-3)/2\rceil$, which justifies the first claim. By Theorem \ref{thm:CM} $\gamma(G) \le 1 + n3^{n-1} - 2\cdot 3^{n-1}$. Therefore, the inequality $1 + n3^{n-1} - 2\cdot 3^{n-1} < 1+\lceil 3^{n-1}(2n-3)/2\rceil$ proves the second claim. \end{proof} \begin{theorem} \label{thm:recursive} For every $n\ge 2$ we have $\gamma(G_{n+1}) \le 3\gamma(G_n) + 3^n - 2$. Consequently, for $n\ge 5$ we have $$\gamma(G_n) \le 3^{n-4}[\gamma(G_4) +27n - 109]+1\le 3^{n-2}[3n- 8]+1.$$ \end{theorem} \begin{proof} Let $\Pi$ be a genus embedding of $G_n$ for some $n\ge 2$. By Proposition \ref{proposition:fcp} and Proposition \ref{proposition:min-genus-short-faces}, the embedding $\Pi$ has a face-covered partition $\mathcal{P}$. By Theorem \ref{thm:construction} applied to $\Pi$ and $\mathcal{P}$, there is an embedding $\Pi'$ of $G_{n+1}$ with $3F_{\Pi} + 3^n$ faces. Using Euler formula on the number of faces of $\Pi$ and $\Pi'$ and the number of vertices and edges of the corresponding graphs yields the first claim. The first closed form of the second claim can be obtained by solving the recurrence relation $g_4 = \gamma(G_4)$ and $g_{n+1} = 3g_{n} + 3^n - 2$ for $n\ge 4$. The second closed form follows from Theorem \ref{thm:CS} as $\gamma(G_4) \le 37$. \end{proof} \begin{corollary} \label{cor:construction} For the genus of $G_5$ we have $\gamma(G_5) \le 190$. \end{corollary} \begin{proof} By Theorem \ref{thm:CS}, there is an embedding $\Pi$ of $G_4$ with genus $37$. The embedding $\Pi$ contains a triangular face and therefore, by Proposition \ref{proposition:fcp}, it admits a face-covered partition $\mathcal{P}$. The result follows by applying Theorem \ref{thm:construction} to $\Pi$ and $\mathcal{P}$. \end{proof} \begin{proof}[Proof of Theorem \ref{thm:main-table}] The lower bounds follow from Theorem \ref{thm:lb} and Proposition \ref{prop:genusTQ}. The upper bounds are proved in Theorem \ref{thm:CS} and Theorem \ref{thm:recursive}. \end{proof} Theorem \ref{thm:construction} and Lemma \ref{proposition:fcp} can be applied also to genus embeddings of $G_2$ and $G_3$ to construct low-genus embeddings of $G_3$ and $G_4$, respectively. In these cases we get that the derived embeddings have genera $10$ and $46$, respectively, yielding $\gamma(G_3) \le 10$ and $\gamma(G_4) \le 46$. Note that both these bounds have been superseded by ad-hoc and computer-search methods of this paper. \section{Discussion} The paper improves the bounds on the genus of $G_n$ by combining computational, recursive, combinatorial, and to a very limited extent also group-theoretic methods. Although at present the search for the genus of $G_n$ seems to be intractable without new techniques, we hope that the gap $30 \leq \gamma(G_4) \leq 37$ is a challenge that will attract mathematicians and computer programmers alike. Any improvement on upper bounds for any $G_n$ with $n\ge 4$ immediately yields better upper bounds for all $G_m$ with $m>n$ by Theorem \ref{thm:recursive}. On the other hand, it would be very desirable to have lower bounds on the genus of $G_n$ that improve on the, in a sense trivial, bounds of Proposition \ref{prop:genusTQ}. Note that there are several related problems worth attacking that were not investigated in this paper, one of them being the determination of the non-orientable genus of $G_n$. The results and methods of this paper may be useful in such an investigation, for instance the inequality $\chi(G_4) \le 57$ derived in Theorem~\ref{thm:lb} directly implies that the non-orientable genus of $G_4$ is at least 59. On the other hand, it is still not known whether the non-orientable genus of $G_3$ is 13 or 14, see \cite{BS}. In our computations we have not considered the fact that $G_n$ is highly symmetric. Therefore, some of the embeddings we have constructed in our search for low-genus embeddings of $G_4$ are pairwise isomorphic. It is possible that a certain speed-up may be achieved by considering only representatives of equivalence classes as is the case in other applications, such as \cite{BCP}. %\footnotesize \subsection*{Acknowledgements} This research was supported from the following sources. The first author was partially supported by APVV-0223-10, Vega 1/1005/12, SK-SI-0025-10, UK/217/2012, Nad\'acia Tatra Banky grant 2010sds121, and by Ministry of Education, Youth, and Sport of Czech Republic, Project No.~CZ.1.07/\-2.3.00/\-30.0009. The second author was partially supported by ARRS project P1-0296. Both authors were partially supported by the EUROCORES Programme EUROGIGA (project GReGAS) of the European Science Foundation, the first author under contract APVV-ESF-EC-0009-10, and the second author under contract N1-0011. Part of the research was done while the first author was visiting the Department of Mathematics of the University of Ljubljana and he would like to thank the host and the department for hospitality. The authors would like to thank also the two anonymous referees for several helpful suggestions. %\bibliographystyle{plain} %\bibliography{bibl} \begin{thebibliography}{99} \bibitem{BH} L.~Beineke and F.~Harary. \newblock The genus of the $n$-cube. \newblock {\em Canad. J. Math.}, 17:494--496, 1965. \bibitem{topics} L.~W. Beineke, R.~J. Wilson, J.~L. Gross, and T.~W. Tucker, editors. \newblock {\em {Topics in Topological Graph Theory}}. \newblock {Encyclopedia of Mathematics and its Applications}. Cambridge University Press, 2009. \bibitem{BW} N.~L. Biggs and A.~T. White. \newblock {\em {Permutation Groups and Combinatorial Structures}}. \newblock Cambridge University Press, 1970. \bibitem{BRS} M.~G. Brin, D.~E. Rauschenberg, and C.~C. Squier. \newblock On the genus of the semidirect product of $Z_9$ by $Z_3$. \newblock {\em J. Graph Theory}, 13(1):49--61, 1989. \bibitem{BS} M.~G. Brin and C.~C. Squier. \newblock {On the genus of $Z_3\times Z_3 \times Z_3$}. \newblock {\em European J. Combin.}, 9:431--443, 1988. \bibitem{BCP} G.~Brinkmann, N.~Van Cleemput, and T.~Pisanski. \newblock Generation of various classes of trivalent graphs. \newblock {\em Theoret. Comput. Sci.} 502:16 -- 29, 2013. \bibitem{conder:1985} M.~D.~E. Conder. \newblock The symmetric genus of alternating and symmetric groups. \newblock {\em J. Combin. Theory Ser. B}, 39:179--186, 1985. \bibitem{duke:1966} R.~A. Duke. \newblock The genus, regional number, and the {B}etti number of a graph. \newblock {\em Canad. J. Math.}, 18:817--822, 1966. \bibitem{GT} J.~L. Gross and T.~W. Tucker. \newblock {\em {Topological Graph Theory}}. \newblock Wiley, 1987. \bibitem{JW} M.~Jungerman and A.~T. White. \newblock On the genus of finite abelian groups. \newblock {\em European J. Combin.}, 1:243--251, 1980. \bibitem{LW} S.~H. Lee and A.~T. White. \newblock Random topological graph theory. \newblock In Y.~Alavi et~al., editor, {\em Proceedings of the Second International Conference in Graph Theory, Combinatorics, Algorithms and Applications}, pp. 234--245. SIAM, 1991. \bibitem{MZ:2003} C.~L. May and J.~Zimmerman. \newblock There is a group of every strong symmetric genus. \newblock {\em Bull. Lond. Math. Soc.}, 35:433--439, 2003. \bibitem{MPSW} B.~Mohar, T.~Pisanski, M.~\v{S}koviera, and A.~T. White. \newblock The cartesian product of three triangles can be embedded into a surface of genus 7. \newblock {\em Discrete Math.}, 56(1):87 -- 89, 1985. \bibitem{NS:1989} R.~Nedela and M.~{\v{S}}koviera. \newblock {The maximum genus of vertex-transitive graphs}. \newblock {\em Discrete Math.}, 78:179--186, 1989. \bibitem{pisanski:1980} T.~Pisanski. \newblock Genus of cartesian products of regular bipartite graphs. \newblock {\em J. Graph Theory}, 4(1):31--42, 1980. \bibitem{pisanski:1982} T.~Pisanski. \newblock Nonorientable genus of cartesian products of regular graphs. \newblock {\em J. Graph Theory}, 6(4):391--402, 1982. \bibitem{PT:1989a} T.~Pisanski and T.~W. Tucker. \newblock The genus of low rank hamiltonian groups. \newblock {\em Discrete Math.}, 78(1-2):157 -- 167, 1989. \bibitem{PT:1989b} T.~Pisanski and T.~W. Tucker. \newblock The genus of the product of a group with an abelian group. \newblock {\em European J. Combin.}, 10, 1989. \bibitem{PW:1988} T.~Pisanski and A.~T. White. \newblock Nonorientable embeddings of groups. \newblock {\em European J. Combin.}, 9:445--461, 1988. \bibitem{RSJTW} B.~Richter, J.~\v{S}ir\'a\v{n}, R.~Jajcay, T.~Tucker, and M.~Watkins. \newblock Cayley maps. \newblock {\em J. Combin. Theory Ser. B}, 95:189--245, 2005. \bibitem{ringel:1955} G.~Ringel. \newblock {\"{U}ber drei kombinatorische Probleme am $n$-dimensionalen W\"{u}rfel und W\"{u}rfelgitter}. \newblock {\em Abh. Math. Sem. Univ. Hamburg}, 20:10--19, 1955. \bibitem{ringel} G.~Ringel. \newblock {\em {Map Color Theorem}}. \newblock Springer, 1974. \bibitem{thomassen:1989} C.~Thomassen. \newblock The graph genus problem is {NP}-complete. \newblock {\em J. Algorithms}, 10:568--576, 1989. \bibitem{thomassen:1997} C.~Thomassen. \newblock The genus problem for cubic graphs. \newblock {\em J. Combin. Theory Ser. B}, 69:52--58, 1997. \bibitem{white:1970} A.~T. White. \newblock The genus of repeated cartesian products of bipartite graphs. \newblock {\em Trans. Amer. Math. Soc.}, 151:393--404, 1970. \bibitem{white:1972} A.~T. White. \newblock On the genus of a group. \newblock {\em Trans. Amer. Math. Soc.}, 173:203--214, 1972. \bibitem{white:2001} A.~T. White. \newblock {\em {Graphs of Groups on Surfaces: Interactions and Models}}. \newblock North Holland, 2001. \end{thebibliography} \end{document}