Biembeddings of Symmetric $n$-Cycle Systems

Abstract

We construct face two-colourable embeddings of the complete graph $K_{2n+1}$ in which every face is a cycle of length $n$; equivalently biembeddings of pairs of symmetric $n$-cycle systems. We prove that the necessary and sufficient condition for the existence of such an embedding in an orientable surface is for $n\ge 3$ to be odd, and in a nonorientable is for $n\ge 4$.

1 Introduction

An $n$ -cycle system of order $v$, $n$-CS$(v)$, is a partition of the edge set of the complete graph on $v$ vertices into cycles of length $n$. Consider a properly face two-coloured embedding of the complete graph $K_v$ in which all the faces are cycles of length $n$, then each colour class corresponds to a $n$-CS$(v)$; this pair of cycle systems is said to biembed in the surface.

In the case where $n=3$, a $3$-CS($v$) is more commonly referred to as a Steiner triple system of order $v$, STS $(v)$. The spectrum for biembeddings of pairs of STS($v$) in orientable surfaces is $v\equiv 3\text { or }7 \,(\text {mod }12)$, [8, 9], while the spectrum for biembeddings of pairs of STS($v$) in nonorientable surfaces is $v\equiv 1\text { or }3 \,(\text {mod }6)$ and $v\ge 9$, [5, 8].

When $n=v$, an $n$-CS$(n)$ corresponds to a partition of the edge set of $K_n$ into Hamilton cycles. In [2], Ellingham and Stephens established the spectrum for biembeddings of pairs of $n$-CS$(n)$ in nonorientable surfaces. The spectrum for orientable biembeddings of pairs of $n$-CS$(n)$ is yet to be resolved.

In this paper we provide both orientable and nonorientable biembeddings for $n$-cycle systems for $n\ge 4$ in nonorientable surfaces and for odd $n\ge 3$ in orientable surfaces. The family of $n$-cycle systems we consider are symmetric $n$ -cycle systems, that is, $n$-cycle systems in which the number of cycles in the partition equals the number of vertices. As each cycle contains $n$ edges such a system is the partition of the edge set of the complete graph $K_{2n+1}$, i.e. an $n$-CS$(2n+1)$.

Suppose we have a biembedding of a pair of $n$-CS($2n+1$) in some surface. Such a biembedding has $2n+1$ vertices, $n(2n+1)$ edges and $2(2n+1)$ faces. If the biembedding is in an orientable surface, by Euler’s formula, $(3-n)(2n+1)=2-2g$, where $g$ is the orientable genus, and hence $n$ is odd. However if the biembedding is in a nonorientable surface, by Euler’s formula, $(3-n)(2n+1)=2-\gamma$, where $\gamma$ is the nonorientable genus, and there is no restriction on the parity of $n$. Further note that there is no triangulation of $K_7$ in a nonorientable surface [3]. Hence necessary conditions for a biembedding of a pair of $n$-CS($2n+1$) are,

• for an orientable embedding, that $n\ge 3$ is odd; and

• for a nonorientable embedding, that $n\ge 4$.

In Sects. 2 and 3 we prove that these necessary conditions are also sufficient.

We will use index 1 current graphs to construct the desired biembeddings of pairs of $n$-CS($2n+1$). We follow the notation established in [7] and recommend this reference to the reader for a more in-depth discussion of current graphs. In particular, suppose that $e$ is an edge in a current graph. If $e$ is orientation preserving, i.e. Type 0, this will be indicated by a superscript 0; whereas, if $e$ is orientation reversing, i.e. Type 1, this will be indicated by a superscript 1. The base graph that we will use is the complete graph on two vertices with edge multiplicity $n$, that is $nK_2$. Clearly $nK_2$ is bipartite and hence, as observed in [4], an index 1 current graph $\langle nK_2\rightarrow S, \mathbb {Z}_{2n+1}\rangle$ induces a proper face two-colouring to its lift. If the current graph $\langle nK_2\rightarrow S, \mathbb {Z}_{2n+1}\rangle$ also satisfies Properties (i), (ii) and (iii) below, then the lift of the current graph is a biembedding of a pair of $n$-CS($2n+1$) (see [6]).

• (i) The embedding $nK_2\rightarrow S$ has one face.

• (ii) Each edge of $nK_2$ is assigned a distinct current from $\mathbb {Z}_{2n+1}$, moreover, if some edge is labelled $i$, then no other edge is labelled $-i$.

• (iii) Let $e_1^{\epsilon _1}\ldots e_n^{\epsilon _n}$, where $\epsilon _i\in \{0,1\}$ for $1\le i\le n$, be the rotation at a vertex $v$ of $nK_2\rightarrow S$ with current $c_i$ carried in the direction of edge $e_i$ that has $v$ as its initial vertex. Then $c_1+\ldots +c_n\equiv 0\,(\text {mod }2n+1)$ and, for all $1\le i\le n$, the sums $\sum _{1\le j\le i}c_j$ are distinct modulo $2n+1$.

Moreover, if $S$ is orientable, then the biembedding is in an orientable surface, while if $S$ is nonorientable, as the order of the current group is odd, the biembedding is in a nonorientable surface (see [7] for details).

Note that a necessary condition for Property (iii) to hold is that there exists a $n$-CS$(2n+1)$ with a cyclic automorphism; i.e. a cyclic $n$ -CS $(2n+1)$. Consider a sequence

$$\begin{aligned} A=(a_0,a_1,\ldots ,a_{n-1}) \end{aligned}$$

where $-n\le a_i\le n$, the $a_i$ are pairwise disjoint and, interpreting $a_n$ as $a_0$ and regarding $k=a_i-a_{i-1}$ as its coset representative modulo $2n+1$ in the range $[-n,n]$,

$$\begin{aligned} \{|a_i-a_{i-1}|\,(\text {mod }2n+1): 1\le i\le n\}=\{1,2,\ldots , n\}. \end{aligned}$$

Then $A$ is a block of a cyclic $n$-CS$(2n+1)$ and generates, under the automorphism $a_i\rightarrow a_i+1\,(\text {mod }2n+1)$, a cyclic $n$-CS$(2n+1)$. We refer to $A$ as a cyclic starter or simply as a starter of the cyclic $n$-CS$(2n+1)$. In [1], Buratti and Del Fra provide a construction for starters for cyclic $n$-CS$(2n+1)$ for all $n\ge 3$; namely $A=(a_0,a_1,\ldots ,a_{n-1})$, where

$$\begin{aligned} a_i= \left\{ \begin{array}{l@{\quad }l} (i+1)(-1)^i;&{} i<(n-2)/2\\ (i+1)(-1)^{i+1};&{} i\ge (n-2)/2. \end{array}\right. \end{aligned}$$

2 Orientable Biembeddings

In this section we will construct the required current graphs to prove the existence of orientable biembeddings of pairs of $n$-CS$(2n+1)$. Hence, for the remainder of this section we assume that $n$ is odd and $n\ge 3$.

Given $A$ as above, the sequence

$$\begin{aligned} A^T=(a_0-a_0,a_0-a_1,\ldots ,a_0-a_{n-1}), \end{aligned}$$

where the entries are adjusted modulo $2n+1$ to be in the range $-n\le a_0-a_i\le n$, is also a starter for a cyclic $n$-CS$(2n+1)$. We call this second starter the transpose of the first.

Consider an embedding $nK_2\rightarrow S$ in which a clockwise orientation is assigned to one vertex, $v_0$ say, and an anticlockwise orientation at the other vertex, $v_1$ say. Suppose that all the edges are Type 0, i.e. orientation preserving, and further suppose that the rotation at $v_0$ equals the rotation at $v_1$. Then as $n$ is odd, the embedding $nK_2\rightarrow S$ has exactly one face and, as all the edges are Type 0, $S$ is orientable.

Denote the rotation at $v_0$ by $e_0,e_1,\ldots ,e_{n-1}$. We direct all the edges from $v_0$ to $v_1$ and label edges $e_i$, interpreting $c_n$ as $c_0$ and $a_n$ as $a_0$, with $c_i=a_i-a_{i-1}$ for $1\le i\le n$. Then the rotation of currents at $v_1$ is $(-c_0,-c_1,\ldots ,-c_{n-1})$. Thus we have constructed a current graph $\langle nK_2\rightarrow S, \mathbb {Z}_{2n+1}\rangle$ that satisfies Properties (i) to (iii). Hence, we have proved the following theorem.

Theorem 1

For all odd $n\ge 3$ there exists a biembedding of a pair of $n$-CS$(2n+1)$ in an orientable surface.

Notice that in the proof of Theorem 1 it is not necessary for the embedding to be of a complete graph. Consider the partial $n$-cycle system $n$-PCS$(mn+1)$, where $m\ge 2$, generated by a cyclic starter $B=(b_0,b_1,\ldots ,b_{n-1})$. This gives a graph decomposition of the subgraph of $K_{mn+1}$, on the vertex set $\{0,1,\ldots ,mn\}$ composed of edges whose endpoints differ by, interpreting $b_n$ as $b_0$, elements of the set $\{|b_i-b_{i-1}|\,(\text {mod }mn+1):1\le i\le n\}$. Then the transpose $n$-PCS$(mn+1)$ generated by $B^T=(b_0-b_0,b_0-b_1,\ldots ,b_0-b_{n-1})$ is a graph decomposition of the same subgraph of $K_{mn+1}$. Then the construction above yields the following theorem.

Theorem 2

For all odd $n\ge 3$ and all $m\ge 2$ a cyclic $n$-PCS$(mn+1)$ generated by a starter $B$ biembeds with the cyclic $n$-PCS$(mn+1)$ generated by $B^T$ in an orientable surface.

We illustrate the above theorem by an example. Let $n=5$ and $m=3$. Consider the cyclic starter $B=(0,1,4,11,6)$, which has transpose $B^T=(0,15,12,5,10)$. This yields a biembedding of a pair of 5-PCS(16) on the subgraph of $K_{16}$ with vertex set $\{0,1,\ldots , 15\}$ composed of edges whose endpoints differ, modulo 16, by elements in $\{1, 3, 5, 6,7\}$.

3 Nonorientable Biembeddings

In the remainder of this paper, to aid the reader, we will denote the rotation at a vertex $v$ as the first row of a table and indicate the label of the edge (taking it to be directed away from $v$) in the row below. Recall that we indicate a Type 1, i.e. orientation reversing, edge by a superscript 1, whereas in the following, an absence of a superscript indicates a Type 0, i.e. orientation preserving, edge. For example consider the current graph $\langle 6K_2\rightarrow S,\mathbb {Z}_{13}\rangle$ in Fig. 1; the rotation at $v_0$ is

$$\begin{aligned} \begin{array}{c|c|c|c|c|c} e_1&{}e_2&{}e_3^1&{}e_4^1&{}e_5&{}e_6^1\\ -2&{}-5&{}-3&{}-1&{}-6&{}4\\ \end{array} \end{aligned}$$

and the rotation at $v_1$ is

$$\begin{aligned} \begin{array}{c|c|c|c|c|c} e_1&{}e_2&{}e_3^1&{}e_5&{}e_6^1&{}e_4^1\\ 2&{}5&{}-3&{}6&{}4&{}-1 \\ \end{array}. \end{aligned}$$

Fig. 1

The current graph $\langle 6K_2\rightarrow S,\mathbb {Z}_{13}\rangle$

3.1 Even Cycles

In this subsection we will consider the case where $n$ is even. We begin by describing an embedding $nK_2\rightarrow S$ that satisfies Property (i) and in which $S$ is a nonorientable surface.

Assign a clockwise orientation to one vertex, $v_0$ say, and an anticlockwise orientation to the other vertex, $v_1$ say. We will denote each of the $n$ edges as $e_i$ where $1\le i\le n$. Now assign edges $e_{n-3}$, $e_{n-2}$ and $e_n$ to be Type 1 and all the other edges to be Type 0. Finally set the rotation at $v_0$ to be

$$\begin{aligned} e_1\;e_2\;e_3\;\ldots \;e_{n-4}\;e_{n-3}^1\;e_{n-2}^1\;e_{n-1}\;e_n^1 \end{aligned}$$

and the rotation at $v_1$ to be

$$\begin{aligned} e_1\;e_2\;e_3\;\ldots \;e_{n-4}\;e_{n-3}^1\;e_{n-1}\;e_n^1\;e_{n-2}^1. \end{aligned}$$

This embedding results in precisely one face, namely

$$\begin{aligned}&e_1\;e_2\;e_3\;\ldots \;e_{n-5}\;e_{n-4}\;e_{n-3}\;e_{n-4}\;e_{n-5}\;\ldots \;e_3\;e_2\;e_1\\&\qquad \qquad e_{n-2}\;e_{n-1}\;e_n\;e_{n-1}\;e_{n-3}\;e_{n-2}\;e_n\;e_1. \end{aligned}$$

As the embedding, $nK_2\rightarrow S$, has both Type 1 and Type 0 edges in parallel, the surface is nonorientable.

All that remains is to establish a labelling so that Properties (ii) and (iii) are satisfied. We consider two cases, where $n\equiv 2\,(\text {mod }4)$ and where $n\equiv 0\,(\text {mod }4)$.

First the case $n\equiv 2\,(\text {mod }4)$. We use the Buratti and Del Fra solution to give the rotation at $v_0$, namely

$$\begin{aligned}&\begin{array}{c|c|c|c|c|} e_1&{}e_2&{}e_3&{}\ldots &{}e_{n-4}\\ a_{n-2}-a_{n-3}&{}a_{n-3}-a_{n-4}&{}a_{n-4}-a_{n-5}&{}\ldots &{}a_3-a_2 \end{array}\\&\qquad \qquad \begin{array}{c|c|c|c} e_{n-3}^1&{}e_{n-2}^1&{}e_{n-1}&{}e_{n}^1\\ a_2-a_1&{}a_1-a_0&{}a_0-a_{n-1}&{}a_{n-1}-a_{n-2} \end{array} \end{aligned}$$

where a label is interpreted as its coset representative modulo $2n+1$ in the range $[-n,n]$. Explicitly, this is the rotation

The rotation at $v_1$ is then

All that remains to be checked is that the rotation at $v_1$ does indeed yield a $n-CS(2n+1)$. To do so consider the sequence of partial sums at $v_1$, namely

$$\begin{aligned} \left( \sum _{1\le j\le i}c_j\right) _{1\le i\le n}= & {} \left( -4,2,-6,4,\ldots ,-\left( \frac{n-2}{2}+2\right) ,\frac{n-2}{2},\right. \\&\quad \;\;\frac{n}{2},-\left( \frac{n}{2}+4\right) ,\frac{n}{2}+2,-\left( \frac{n}{2}+6\right) ,\ldots ,n-5,-(n-1),\\&\quad \;\;-(n-6),5,3,0\bigg ). \end{aligned}$$

The set of the first $n/2-1$ partial sums is

$$\begin{aligned} X=\{-(2i+2),2i: 1\le i\le (n-2)/4\}; \end{aligned}$$

the set of the partial sums from $n/2$ to $n-4$ is

$$\begin{aligned} Y=\{n/2+2i,-(n/2+4+2i): 0\le i\le (n-10)/4\};\text { and} \end{aligned}$$

the remaining partial sums are the elements of the set

$$\begin{aligned} Z=\{-(n-6),5,3,0\}. \end{aligned}$$

If $n-6>((n-2)/2+2)=n/2+1$, then $n>14$ and $|X\cup Y\cup Z|=n$. Hence for $n>14$ and $n\equiv 2\,(\text {mod }4)$ we have a biembedding of a pair of $n$-CS$(2n+1)$.

Next we consider the case $n\equiv 0\,(\text {mod }4)$. Again we use the Buratti and Del Fra solution to establish the rotation at $v_0$, namely

This time the rotation at $v_1$ is

In this case the set of the first $n/2-1$ partial sums is

$$\begin{aligned} X=\{-(2i+2),2i: 1\le i\le (n-4)/4\}\,\cup \,\{-(n/2+2)\}; \end{aligned}$$

the set of the partial sums from $n/2$ to $n-5$ is

$$\begin{aligned} Y=\{-(n/2+3+2i),n/2+1+2i: 0\le i\le (n-12)/4\};\text { and} \end{aligned}$$

the set of the remaining four partial sums is

$$\begin{aligned} Z=\{n+2,-(n-6),5,3,0\}. \end{aligned}$$

If $n-6>n/2+2$, then $n>16$ and $|X\cup Y\cup Z|=n$. Hence for $n>16$ and $n\equiv 0\,(\text {mod }4)$ we have a biembedding of a pair of $n$-CS$(2n+1)$.

3.2 Odd Cycles

We consider six cases, corresponding to residue classes modulo 12. In the cases where $n\equiv 1,3,5,7,11\,(\text {mod }12)$ the rotation about $v_0$ is obtained from the Buratti and Del Fra solution. When $n\equiv 9\,(\text {mod }12)$ the rotation at $v_0$ is slightly different, with two terms of the Buratti and Del Fra solution transposed. In all cases we will make repeated use of the following lemma.

Lemma 1

Let $n\ge 5$ be an odd integer. Consider an embedding of the graph $nK_2$ with vertices $v_0$ and $v_1$ in a surface $S$. Suppose that there are rotations assigned to $v_0$ and $v_1$ and types assigned to the edges of $nK_2$ so that $nK_2\rightarrow S$ has only one face. Further suppose that there are edges $a$, $b$, $c$ and $d$ that are all Type 0 and the rotations at $v_0$ and $v_1$ are

$$\begin{aligned} v_0:\;\ldots \;a\;b\;c\;d\;\ldots \quad \text { and }\quad v_1:\;\ldots \;a\;b\;c\;d\;\ldots \end{aligned}$$

Then by changing $b$ and $c$ to be Type 1 and the rotation at $v_1$ to be

$$\begin{aligned} v_1:\;\ldots \;a\;c\;b\;d\;\ldots \end{aligned}$$

we obtain an embedding $nK_2\rightarrow S'$ where $S'$ is nonorientable and in which the embedding has only one face.

Proof

The embedding $nK_2\rightarrow S$ has only one face, the facial walk of which is either

$$\begin{aligned} W_1=\;\ldots \;a\;b\;c\;d\;\dots \;a\;b\;c\;d\;\ldots \quad \text { or }\quad W_2=\;\ldots \;a\;b\;c\;d\;\dots \;d\;c\;b\;a\;\ldots \end{aligned}$$

Changing $b$ and $c$ to be Type 1 and the rotation at $v_1$ to be

$$\begin{aligned} v_1:\;\ldots \;a\;c\;b\;d\;\ldots \end{aligned}$$

the facial walk becomes one of either

$$\begin{aligned} W_1'=\;\ldots \;a\;c\;b\;d\;\dots \;a\;b\;c\;d\;\ldots \quad \text { or }\quad W_2'=\;\ldots \;a\;c\;b\;d\;\dots \;d\;c\;b\;a\;\ldots \end{aligned}$$

As the embedding has Type 0 and Type 1 edges in parallel it is necessarilly nonorientable. $\square$

For each of the odd residue classes modulo 12 we start with a copy of $nK_2$ in which one vertex, $v_0$ say, is assigned a clockwise orientation and the other vertex, $v_1$ say, is assigned an anticlockwise orientation and all the edges are assigned to be Type 0. We also set the rotations of both $v_0$ and $v_1$ to be $e_1\;e_2\;\ldots \;e_{n-1}\;e_n$. As noted in Sect. 2, this embedding has precisely one face. To this embedding we will repeatedly apply Lemma 1 to obtain embeddings of $nK_2$ in nonorientable surfaces that satisfy Property (i).

We will present the constructions in the following format. First we list the set of edges to which Lemma 1 is applied. When $n\equiv 9\,(\text {mod }12)$ we give the rotations at $v_0$ and $v_1$. When $n\not \equiv 9\,(\text {mod }12)$ the rotation at $v_0$ corresponds to the Buratti and Del Fra solution and hence we just give the rotation at $v_1$. We then form the set of partial sums to verify that $v_1$ (and when $n\equiv 9\,(\text {mod }12)$ also $v_0$) yields an $n$-CS$(2n+1)$.

3.2.1 ${\mathbf n=12k+1}$

Apply Lemma 1 to the 4-tuples in the set

$$\begin{aligned} \big \{(e_{6k+2+3j},e_{6k+3+3j},e_{6k+4+3j}, e_{6k+5+3j}): 0 \le j\le 2k-1\big \}. \end{aligned}$$

The rotation at $v_1$ is

$$\begin{aligned}&\displaystyle \begin{array}{c|} e_1\\ 1 \end{array} \left[ \begin{array}{c|c} e_{2i+2}&{}e_{2i+3}\\ 12k-4i&{}-(12k-2-4i) \end{array}\right] _{0\le i\le 3k-1} \begin{array}{|c|} e_{6k+2}\\ 12k+1 \end{array}\\&\displaystyle \quad \left[ \begin{array}{c|c|c|c|c|c} e_{6(k+i)+4}^1&{}e_{6(k+i)+3}^1&{}e_{6(k+i)+5}&{}e_{6(k+i)+7}^1&{}e_{6(k+i)+6}^1&{}e_{6(k+i)+8}\\ 12i+5&{}-(12i+3)&{}12i+7&{}-(12i+11)&{}12i+9&{}-(12i+13) \end{array}\right] _{0\le i\le k-2}\\&\displaystyle \begin{array}{|c|c|c|c|c} e_{12k-2}^1&{}e_{12k-3}^1&{}e_{12k-1}&{}e_{12k+1}^1&{}e_{12k}^1\\ 12k-7&{}-(12k-9)&{}12k-5&{}-(12k-1)&{}12k-3 \end{array}. \end{aligned}$$

The set of partial sums, working modulo $24k+3$, is

$$\begin{aligned}&\{2i+1,12k+1-2i: 0\le i\le 3k-1\}\,\cup \,\{6k+1\}\,\cup \,\{-(6(k+i)+1),-(6(k-i)-4),\\&\quad -(6(k+i)-1),-(6(k-i)-8),-(6(k+i)+3),-(6(k-i)-6): 0\le i\le k-2\}\,\cup \\&\quad \{-12k+5,-2,-(12k-7),2,-(12k-3),0\}. \end{aligned}$$

This set has cardinality $n$ for all $n\ge 13$.

3.2.2 ${\mathbf n=12k+3}$

Apply Lemma 1 to the 4-tuples in the set

$$\begin{aligned} \big \{(e_{6k+4+3j},e_{6k+5+3j},e_{6k+6+3j}, e_{6k+7+3j}): 0 \le j\le 2k-1\big \}. \end{aligned}$$

The rotation at $v_1$ is

$$\begin{aligned}&\displaystyle \begin{array}{c|} e_1\\ -1 \end{array} \left[ \begin{array}{c|c} e_{2i+2}&{}e_{2i+3}\\ -(12k+2-4i)&{}12k-4i \end{array}\right] _{0\le i\le 3k-1} \begin{array}{|c|c|} e_{6k+2}&{}e_{6k+3}\\ -2&{}12k+3 \end{array}\\&\displaystyle \left[ \begin{array}{c|c|c|c|c|c} e_{6(k+i)+4}&{}e_{6(k+i)+6}^1&{}e_{6(k+i)+5}^1&{}e_{6(k+i)+7}&{}e_{6(k+i)+9}^1&{}e_{6(k+i)+8}^1\\ 12i+3&{}-(12i+7)&{}12i+5&{}-(12i+9)&{}12i+13&{}-(12i+11) \end{array}\right] _{0\le i\le k-1}. \end{aligned}$$

The set of partial sums, working modulo $24k+7$, is

$$\begin{aligned}&\{-(2i+1),-(12k+3-2i): 0\le i\le 3k-1\}\,\cup \,\{-(6k+1),-(6k+3)\}\,\cup \\&\quad \{6(k-i),6(k+i)+3,6(k-i)-4,6(k+i)+1,6(k-i)-8,\\&\quad 6(k+i)+5: 0\le i\le k-1\}\,\cup \,\{0\}. \end{aligned}$$

This set has cardinality $n$ for all $n\ge 15$.

3.2.3 ${\mathbf n=12k+5}$

Apply Lemma 1 to the 4-tuples in the set

$$\begin{aligned} \{((e_{6k+5+3j},e_{6k+6+3j},e_{6k+7+3j},e_{6k+8+3j}): 0 \le j\le 2k-1\}. \end{aligned}$$

The rotation at $v_1$ is

$$\begin{aligned}&\displaystyle \begin{array}{c|} e_1\\ 1 \end{array} \left[ \begin{array}{c|c} e_{2i+2}&{}e_{2i+3}\\ 12k+4-4i&{}-(12k+2-4i) \end{array}\right] _{0\le i\le 3k} \begin{array}{|c|} e_{6k+4}\\ 12k+5 \end{array} \left[ \begin{array}{c|} e_{6(k+i)+5}\\ 12i+3 \end{array}\right. \\&\displaystyle \left. \begin{array}{c|c|c|c|c} e_{6(k+i)+7}^1&{}e_{6(k+i)+6}^1&{}e_{6(k+i)+8}&{}e_{6(k+i)+10}^1&{}e_{6(k+i)+9}^1\\ -(12i+7)&{}12i+5&{}-(12i+9)&{}12i+13&{}-(12i+11) \end{array}\right] _{0\le i\le k-1} \begin{array}{|c} e_{12k+5}\\ 12k+3 \end{array}. \end{aligned}$$

The set of partial sums, working modulo $24k+11$, is

$$\begin{aligned}&\{2i+1,12k+5-2i: 0\le i\le 3k\}\,\cup \,\{6k+3\}\,\cup \,\{-(6(k+i)+3),-(6(k-i)),\\&\quad -(6(k\!+\!i)\!+\!7),-(6(k\!-\!i)\!+\!2),-(6(k\!+\!i)\!+\!11),-(6(k\!-\!i)\!-\!2): 0\!\le \! i\!\le \!k-1\}\,\cup \\&\quad \{-(12k+3),0\}. \end{aligned}$$

This set has cardinality $n$ for all $n\ge 17$.

3.2.4 ${\mathbf n=12k+7}$

Apply Lemma 1 to the 4-tuples in the set

$$\begin{aligned} \{(e_{3j+2},e_{3j+3},e_{3j+4},e_{3j+5}): 0 \le j\le 4k+1\}. \end{aligned}$$

The rotation at $v_1$ is

$$\begin{aligned}&v_1:\begin{array}{c|c|c|c|} e_1&{}e_2&{}e_4^1&{}e_3^1\\ -1&{}-(12k+6)&{}12k+2&{}-(12k+4) \end{array} \left[ \begin{array}{c|c|c|} e_{6i+5}&{}e_{6i+7}^1\\ 12(k-i)&{}-(12(k-i)-4) \end{array}\right. \\&\quad \left. \begin{array}{c|c|c|c} e_{6i+6}^1&{}e_{6i+8}&{}e_{6i+10}^1&{}e_{6i+9}^1\\ 12(k-i)-2&{}-(12(k-i)-6)&{}12(k-i)-10&{}-(12(k-i)-8) \end{array}\right] _{0\le i\le k-1}\\&\quad \begin{array}{|c|} e_{6k+5}\\ 12k+7 \end{array} \left[ \begin{array}{c|c|c|c|c} e_{6(k+i)+7}^1&{}e_{6(k+i)+6}^1&{}e_{6(k+i)+8}&{}e_{6(k+i)+10}^1&{}e_{6(k+i)+9}^1\\ 12i+5&{}-(12i+3)&{}12i+7&{}-(12i+11)&{}12i+9 \end{array}\right. \\&\qquad \left. \begin{array}{c} e_{6(k+i)+11}\\ -(12i+13) \end{array}\right] _{0\le i\le k-1} \begin{array}{|c|c} e_{12k+7}^1&{}e_{12k+6}^1\\ 12k+5&{}-(12k+3) \end{array}. \end{aligned}$$

The set of partial sums, working modulo $24k+15$, is

$$\begin{aligned}&\{-1,-(12k+7),-5\}\,\cup \,\{-(12k+9-6i), -(6i\!+\!9), -(12k\!+\!5\!-\!6i), -(6i\!+\!7),\\&\quad -(12k+1-6i),-(6i+11): 0\le i\le k-1\}\,\cup \,\{-(6k+9)\}\,\cup \,\{6(k-i)-2,\\&\quad 6(k+i)+3,6(k\!-\!i),6(k\!+\!i)+7,6(k\!-\!i)-4,6(k\!+\!i)\!+\!5: 0\le i\le k-1\}\,\cup \\&\quad \{-2,12k+3,0\}. \end{aligned}$$

This set has cardinality $n$ for all $n\ge 7$.

3.2.5 ${\mathbf n=12k+9}$

Apply Lemma 1 to the 4-tuples in the set

$$\begin{aligned}&\{(e_{3j-1},e_{3j},e_{3j+1},e_{3j+2}): 1 \le j\le 2k+1\}\,\cup \\&\quad \{(e_{6k+3j+7},e_{6k+3j+8},e_{6k+3j+9},e_{6k+3j+10}): 0 \le j\le 2k\}. \end{aligned}$$

The rotation at $v_0$ is

$$\begin{aligned}&\begin{array}{c|} e_1\\ -1 \end{array} \left[ \begin{array}{c|c|c|c|} e_{6i+2}&{}e_{6i+3}^1&{}e_{6i+4}^1&{}e_{6i+5}\\ -(12(k-i)+8)&{}12(k-i)+6&{}-(12(k-i)+4)&{}12(k-i)+2 \end{array}\right. \\&\quad \left. \begin{array}{c|c} e_{6i+6}^1&{}e_{6i+7}^1\\ -12(k-i)&{}12(k-i)-2 \end{array}\right] _{0\le i\le k-1}\begin{array}{|c|c|c|c|c|} e_{6k+2}&{}e_{6k+3}^1&{}e_{6k+4}^1&{}e_{6k+5}&{}e_{6k+6}\\ -8&{}6&{}-4&{}-(12k+9)&{}2 \end{array}\\&\quad \left[ \begin{array}{c|c|c|c|c|c} e_{6k+6i+7}&{}e_{6k+6i+8}^1&{}e_{6k+6i+9}^1&{}e_{6k+6i+10}&{}e_{6k+6i+11}^1&{}e_{6k+6i+12}^1\\ -(12i+3)&{}12i+5&{}-(12i+7)&{}12i+9&{}-(12i+11)&{}12i+13 \end{array}\right] _{0\le i\le k-1}\\&\quad \begin{array}{|c|c|c} e_{12k+7}&{}e_{12k+8}^1&{}e_{12k+9}^1\\ -(12k+3)&{}12k+5&{}-(12k+7) \end{array}. \end{aligned}$$

The set of partial sums for this rotation, working modulo $24k+19$, is

$$\begin{aligned}&\{-(6i+1),-(12k+9-6i),-(6i+3),-(12k+7-6i),-(6i+5),\\&\quad -(12k\!+\!5\!-\!6i): 0\!\le \! i\!\le \! k-1\}\,\cup \,\{-(6k+1), -(6k+9), -(6k+3), -(6k+7),\\&\quad 6k+3)\}\,\cup \,\{6(k+i)+5,6(k-i)+2,6(k+i)+7,6(k-i),6(k+i)+9,\\&\quad 6(k-i)-2: 0\le i\le k-1\}\,\cup \,\{12k+5,2,12k+7,0\}. \end{aligned}$$

The rotation at $v_1$ is

$$\begin{aligned}&\begin{array}{c|} e_1\\ 1 \end{array} \left[ \begin{array}{c|c|c|c|} e_{6i+2}&{}e_{6i+4}^1&{}e_{6i+3}^1&{}e_{6i+5}\\ 12(k-i)+8&{}-(12(k-i)+4)&{}12(k-i)+6&{}-(12(k-i)+2) \end{array}\right. \\&\quad \left. \begin{array}{c|c} e_{6i+7}^1&{}e_{6i+6}^1\\ 12(k-i)-2&{}-12(k-i) \end{array}\right] _{0\le i\le k-1}\begin{array}{|c|c|c|c|c|} e_{6k+2}&{}e_{6k+4}^1&{}e_{6k+3}^1&{}e_{6k+5}&{}e_{6k+6}\\ 8&{}-4&{}6&{}12k+9&{}-2 \end{array}\\&\quad \left[ \begin{array}{c|c|c|c|c} e_{6k+6i+7}&{}e_{6k+6i+9}^1&{}e_{6k+6i+8}^1&{}e_{6k+6i+10}&{}e_{6k+6i+12}^1\\ 12i+3&{}-(12i+7)&{}12i+5&{}-(12i+9)&{}12i+13 \end{array}\right. \\&\quad \left. \begin{array}{c} e_{6k+6i+11}^1\\ -(12i+11) \end{array}\right] _{0\le i\le k-1} \begin{array}{|c|c|c} e_{12k+7}&{}e_{12k+9}^1&{}e_{12k+8}^1\\ 12k+3&{}-(12k+7)&{}12k+5 \end{array}. \end{aligned}$$

The set of partial sums, working modulo $24k+19$, is

$$\begin{aligned}&\{6i\!+\!1,12k\!+\!9\!-\!6i,6i\!+\!5,12k+11-6i,6i+9,12k+7-6i: 0\le i\le k-1\}\,\cup \\&\quad \{6k+1, 6k+9, 6k+5, 6k+11, -(6k-1)\}\,\cup \\&\quad \{-(6(k+i)+1),-(6(k-i)-2),-(6(k+i)+5),-6(k-i),-(6(k+i)+9),\\&\quad -(6(k-i)-4): 0\le i\le k-1\}\,\cup \,\{-(12k+1),2,-(12k+5),0\}. \end{aligned}$$

Both sets of partial sums have cardinality $n$ for all $n\ge 21$.

3.2.6 ${\mathbf n=12k+11}$

Apply Lemma 1 to the 4-tuples in the set

$$\begin{aligned} \{(e_{3j+1},e_{3j+2},e_{3j+3},e_{3j+4}): 0 \le j\le 2k+1\}. \end{aligned}$$

The rotation at $v_1$ is

$$\begin{aligned}&\begin{array}{c|c|c|c|c|c|} e_1&{}e_3^1&{}e_2^1&{}e_4&{}e_6^1&{}e_5^1\\ -1&{}-(12k+8)&{}12k+10&{}-(12k+6)&{}12k+2&{}-(12k+4) \end{array} \left[ \begin{array}{c|} e_{6i+7}\\ 12(k-i) \end{array}\right. \\&\quad \begin{array}{c|c|c|c|} e_{6i+9}^1&{}e_{6i+8}^1&{}e_{6i+10}&{}e_{6i+12}^1\\ -(12(k-i)-4)&{}12(k-i)-2&{}-(12(k-i)-6)&{}12(k-i)-10 \end{array}\\&\quad \left. \begin{array}{|c} e_{6i+11}^1\\ -(12(k-i)-8) \end{array}\right] _{0\le i\le k-1}\begin{array}{|c|} e_{6k+7}\\ 12k+11 \end{array} \left[ \begin{array}{c|c} e_{6k+8+2i}&{}e_{6k+9+2i}\\ 4i+3&{}-(4i+5) \end{array}\right] _{0\le i\le 3k+1}. \end{aligned}$$

The set of partial sums, working modulo $24k+23$, is

$$\begin{aligned}&\{-1,-(12k+9),1,-(12k+5),-3\}\,\cup \,\{-(12k+7-6i), -(6i+7),\\&\quad -(12k+3-6i),-(6i+5),-(12k-1-6i),-(6i+9): 0\le i\le k-1\}\,\cup \\&\quad \{-(6k+7)\}\,\cup \,\{6k+4-2i,6k+7+2i: 0\le i\le 3k+1\}\,\cup \,\{0\}. \end{aligned}$$

This set has cardinality $n$ for all $n\ge 11$.

3.3 Small Designs

The results in Sects. 3.1 and 3.2 establish for $n\ge 4$ the existence of a biembedding of a pair of $n$-CS($2n+1$) in a nonorientable surface except when $n\in \{4,5,6,8,9,10,12,14,16\}$. In this subsection we deal with these values. Note that a current graph yielding a 6-CS(13) is given in Fig. 1.

The pair, $(A_4,B_4)$, of 4-CS(9)s biembed in a nonorientable surface as do the pair, $(A_5,B_5)$, of 5-CS(11)s.

		$A_5$	$B_5$
$A_4$	$B_4$	$(0,8,7,3,5)$	$(7,0,4,10,5)$
$(0,1,5,3)$	$(3,0,4,1)$	$(1,9,8,4,6)$	$(2,0,10,8,4)$
$(1,2,6,4)$	$(8,0,2,4)$	$(2,10,9,5,7)$	$(3,0,5,4,1)$
$(2,3,7,5)$	$(6,0,7,5)$	$(3,0,10,6,8)$	$(8,0,9,6,3)$
$(3,4,8,6)$	$(5,0,1,2)$	$(4,1,0,7,9)$	$(6,0,1,10,2)$
$(4,5,0,7)$	$(7,1,8,6)$	$(5,2,1,8,10)$	$(8,1,7,3,2)$
$(5,6,1,8)$	$(6,1,5,4)$	$(6,3,2,9,0)$	$(5,1,6,7,8)$
$(6,7,2,0)$	$(3,2,7,4)$	$(7,4,3,10,1)$	$(9,1,2,7,10)$
$(7,8,3,1)$	$(6,2,8,3)$	$(8,5,4,0,2)$	$(9,2,5,3,4)$
$(8,0,4,2)$	$(5,3,7,8)$	$(9,6,5,1,3)$	$(10,3,9,5,6)$
		$(10,7,6,2,4)$	$(6,4,7,9,8)$

Finally, we present rotations at $v_0$ and $v_1$ that provide current graphs that yield nonorientable biembeddings of pairs of $n$-CS$(2n+1)$ for $n\in \{8,9,10,12,14,16\}$. It is straightforward to verify that each current graph has only one face.

${\mathbf n=8}$

$$\begin{aligned}&v_0: \quad \begin{array}{c|c|c|c|c|c|c|c} e_1&{}e_2&{}e_3&{}e_4&{}e_5^1&{}e_6^1&{}e_7&{}e_8^1\\ -7&{}-3&{}5&{}1&{}8&{}-6&{}4&{}-2\\ \end{array}\\&v_1: \quad \begin{array}{c|c|c|c|c|c|c|c} e_1&{}e_2&{}e_3&{}e_4&{}e_5^1&{}e_7&{}e_8^1&{}e_6^1\\ 7&{}3&{}-5&{}-1&{}8&{}-4&{}-2&{}-6 \end{array} \end{aligned}$$

${\mathbf n=9}$

$$\begin{aligned}&v_0: \quad \begin{array}{c|c|c|c|c|c|c|c|c} e_1&{}e_2&{}e_3&{}e_4&{}e_5^1&{}e_6^1&{}e_7&{}e_8&{}e_9^1\\ -3&{}5&{}-7&{}-1&{}-8&{}6&{}-4&{}-9&{}2\\ \end{array}\\&v_1: \quad \begin{array}{c|c|c|c|c|c|c|c|c} e_1&{}e_2&{}e_3&{}e_4&{}e_7&{}e_5^1&{}e_8&{}e_9^1&{}e_6^1\\ 3&{}-5&{}7&{}1&{}4&{}-8&{}9&{}2&{}6 \end{array} \end{aligned}$$

${\mathbf n=10}$

$$\begin{aligned}&v_0: \quad \begin{array}{c|c|c|c|c|c|c|c|c|c} e_1&{}e_2&{}e_3&{}e_4&{}e_5&{}e_6&{}e_7^1&{}e_8^1&{}e_9&{}e_{10}^1\\ -9&{}-3&{}5&{}-7&{}-1&{}4&{}8&{}-6&{}-10&{}-2\\ \end{array}\\&v_1: \quad \begin{array}{c|c|c|c|c|c|c|c|c|c} e_1&{}e_2&{}e_3&{}e_4&{}e_5&{}e_6&{}e_7^1&{}e_9&{}e_{10}^1&{}e_{8}^1\\ 9&{}3&{}-5&{}7&{}1&{}-4&{}8&{}10&{}-2&{}-6 \end{array} \end{aligned}$$

${\mathbf n=12}$

$$\begin{aligned}&{v_0:}\quad \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c} e_1^1&{}e_2^1&{}e_3&{}e_4^1&{}e_5&{}e_6&{}e_7&{}e_8&{}e_9&{}e_{10}&{}e_{11}&{}e_{12}\\ 9&{}1&{}12&{}-10&{}8&{}-6&{}-7&{}-2&{}-3&{}4&{}5&{}-11\\ \end{array}\\&v_1: \quad \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c} e_1^1&{}e_3&{}e_4^1&{}e_5&{}e_6&{}e_2^1&{}e_7&{}e_8&{}e_9&{}e_{10}&{}e_{11}&{}e_{12}\\ 9&{}-12&{}-10&{}-8&{}6&{}1&{}7&{}2&{}3&{}-4&{}-5&{}11 \end{array} \end{aligned}$$

${\mathbf n=14}$

$$\begin{aligned}&{v_0:} \quad \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c} e_1^1&{}e_2^1&{}e_3&{}e_4^1&{}e_5&{}e_6&{}e_7&{}e_8&{}e_9&{}e_{10}&{}e_{11}&{}e_{12}&{}e_{13}&{}e_{14}\\ -11&{}-1&{}-14&{}12&{}-10&{}8&{}-6&{}-13&{}-7&{}9&{}5&{}-3&{}4&{}-2\\ \end{array}\\&v_1: \quad \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c} e_1^1&{}e_3&{}e_4^1&{}e_5&{}e_6&{}e_7&{}e_2^1&{}e_8&{}e_9&{}e_{10}&{}e_{11}&{}e_{12}&{}e_{13}&{}e_{14}\\ -11&{}14&{}12&{}10&{}-8&{}6&{}-1&{}13&{}7&{}-9&{}-5&{}3&{}-4&{}2 \end{array} \end{aligned}$$

${\mathbf n=16}$

$$\begin{aligned}&v_0: \quad \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} e_1&{}e_2&{}e_3&{}e_4&{}e_5&{}e_6&{}e_7&{}e_8&{}e_9&{}e_{10}&{}e_{11}^1&{}e_{12}^1&{}e_{13}&{}e_{14}&{}e_{15}&{}e_{16}^1\\ -15&{}-3&{}5&{}-7&{}9&{}-11&{}13&{}16&{}1&{}-14&{}-2&{}12&{}8&{}-6&{}4&{}-10\\ \end{array}\\&v_1: \quad \begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} e_1&{}e_2&{}e_3&{}e_4&{}e_5&{}e_6&{}e_7&{}e_8&{}e_9&{}e_{10}&{}e_{11}^1&{}e_{13}&{}e_{14}&{}e_{15}&{}e_{16}^1&{}e_{12}^1\\ 15&{}3&{}-5&{}7&{}-9&{}11&{}-13&{}-16&{}-1&{}14&{}-2&{}-8&{}6&{}-4&{}-10&{}12 \end{array} \end{aligned}$$

Having dealt with these small cases we have completed the proof of the following theorem.

Theorem 3

For all $n\ge 4$ there exists a biembedding of a pair of $n$-CS$(2n+1)$ in a nonorientable surface.