Regular Maps of High Density

Abstract

A regular map is a surface together with an embedded graph, having properties similar to those of the surface and graph of a platonic solid. We analyze regular maps with reflection symmetry and a simple graph with ratio between vertex-degree and number of vertices strictly exceeding $\frac{1}{2}$. We conclude that all regular maps of this type belong to a family of maps naturally defined on the Fermat curves $x^n+y^n+z^n=0$, excepting the one corresponding to the tetrahedron.

1 Introduction

Objects of high symmetry have been of interest for a long time. Thousands of years ago, the Greeks already studied the platonic solids, regular convex polyhedra with congruent faces of regular polygons such that the same number of faces meet at each vertex. The Greeks proved that there are only five of them: the tetrahedron, the cube, the octahedron, the dodecahedron, and the icosahedron.

One can consider the platonic solids to be orientable surfaces of genus 0 with an embedded graph satisfying certain properties. The natural question is then whether this concept can be generalized. This leads to the notion of regular maps. Regular maps have also been studied for many years (see for example [8]).

In contrast to the succinct and complete list of platonic solids, a complete classification for regular maps seems far off, but at least a few families of regular maps are known. Investigations into these objects is of great interest, amongst other reasons because of their intriguing connection to algebraic curves. Regular maps are special cases of dessins d’enfants [7]. As such, the combinatorial structure of vertices, edges, and faces gives rise not only to a topological realisation, but even to a unique algebraic curve! Explicitly computing an ideal that defines some complex projective realisation of this algebraic curve for a given regular map is an ongoing area of research.

Two happy examples of a whole family of regular maps for which the algebraic curves are known, are naturally defined on the Fermat curves $x^n+y^n+z^n=0$. For a given Fermat curve one has to consider the action on this complex algebraic curve (and hence a real surface) of its group of algebraic automorphisms, which turn out to be realizable by linear maps in $\mathbb {C}^3$. A map presentation (see Sect. 2) of these maps was described concisely by Coxeter and Moser (see [4]), although they did not hint at the link to the Fermat curves, and were perhaps not aware of it. We give a more detailed description of the Fermat family in Sect. 2.

Regular maps can broadly be divided into two classes: chiral and reflexive. We will deal only incidentally with chiral maps. In low genus, all regular maps have been computed, with a list of reflexive maps up to genus 15 appearing in [3] and with more recent lists at [2], which runs up to genus 301 for reflexive maps at the time of writing.

The combinatorial aspect of a regular map that is the focus of this paper is its (graph) density, defined in Sect. 2. One discovers from studying the maps of low genus, that having a high density is relatively rare. In fact, the only reflexive regular maps of low genus with simple graphs of density strictly exceeding $\frac{1}{2}$ are members of the Fermat family (every vertex in its graph being connected to precisely two thirds of the vertices), the sole exception being the tetrahedral map, by which we mean the regular map corresponding to the natural embedding of the tetrahedron in the sphere. This naturally leads to the question whether this is true in higher genus as well. This paper answers this question by classifying all reflexive regular maps with simple graphs of density strictly exceeding $\frac{1}{2}$.

Theorem 1.1

(Regular map density theorem) A regular map on v vertices with a simple underlying graph and degree strictly exceeding $\frac{v}{2}$ is either chiral, or a member of the Fermat family, or the tetrahedral map.

One interesting corollary of this theorem is the following. All complete graphs $K_n$ can be embedded as regular maps for $n \ge 3$. Whereas $K_3$ can be embedded as the simplest Fermat map, and $K_4$ yields the tetrahedral map, all regular embeddings for $n \ge 5$ must be chiral. A more straightforward proof of that fact can also be found in [5].

Before proving this theorem in Sect. 3, we will give the definition of a regular map, show some properties of regular maps, and define the Fermat maps.

2 Background

Let us now give a more formal definition of regular maps.

Definition 2.1

A map ${\mathbf {M}}$ is an orientable surface $\Sigma$ together with an embedded connected finite graph $\Gamma$ with non-empty vertex set ${\mathrm {V}}$ and non-empty edge set ${\mathrm {E}}$ such that the complement of $\varGamma$ in ${\mathbf {M}}$ is a finite disjoint union of open discs. Each of these open discs is called a face of $\varGamma$. If $v \in {\mathrm {V}}$, $e \in {\mathrm {E}}$ and f is a face of $\varGamma$, we call any pair of these incident if one of the pair is contained in the closure of the other.

A cellular homeomorphism of ${\mathbf {M}}$ is a homeomorphism of ${\mathbf {M}}$ that induces a graph automorphism of $\varGamma$. An automorphism of ${\mathbf {M}}$ is an equivalence class of cellular homeomorphisms under the equivalence relation of isotopy. We denote the set of automorphisms of ${\mathbf {M}}$ by ${{\text {Aut}}({{\mathbf {M}}})}$, and we write ${{\text {Aut}}^+({{\mathbf {M}}})}$ for the set of orientation-preserving automorphisms of ${\mathbf {M}}$. We call ${\mathbf {M}}$ chiral if ${{\text {Aut}}^+({{\mathbf {M}}})} = {{\text {Aut}}({{\mathbf {M}}})}$ and we call ${\mathbf {M}}$ reflexive otherwise. Below we will refer to reflexive maps with the symbol ${\mathbf {R}}$ to stress that this property is assumed.

A map ${\mathbf {M}}$ is called regular if for all directed $\overrightarrow{e},\overrightarrow{e'} \in {\mathrm {E}}$ there is an orientation-preserving automorphism of ${\mathbf {M}}$ mapping $\overrightarrow{e}$ to $\overrightarrow{e'}$.

Example 2.2

The platonic solids correspond to regular maps, simply by interpreting the traditional terms ‘vertices’ and ‘faces’ according to our definition above, and defining the embedded graph by rereading the term ‘edges’. The tetrahedral map, the one resulting from the tetrahedron, plays an important role in this article.

Notation 2.3

If ${\mathbf {M}}$ is a map, we denote by $\varSigma ({\mathbf {M}})$, $\varGamma ({\mathbf {M}})$, ${\mathrm {V}}({\mathbf {M}})$ and ${\mathrm {E}}({\mathbf {M}})$ the corresponding surface, graph, vertex set and edge set. The set of faces of ${\mathbf {M}}$ is denoted ${\mathrm {F}}({\mathbf {M}})$.

Note that any cellular homeomorphism is uniquely determined up to cellular isotopy by the graph isomorphism it induces (although in general, not all graph isomorphisms are representable by a cellular homeomorphism).

Lemma 2.4

Let ${\mathbf {M}}$ be a map. Suppose $\phi \in {{\text {Aut}}^+({{\mathbf {M}}})}$ fixes some directed edge $\overrightarrow{e}$. Then $\phi = {{\text {Id}}}$.

Proof

Suppose $e'$ is an edge such that e and $e'$ share a common vertex. Let v be a vertex incident to both e and $e'$ and consider a local picture around v. The only way for $\phi$ to fix $\overrightarrow{e}$ and to preserve orientation is to act as the identity locally. In particular, this means it must fix $\overrightarrow{e'}$ as well. Using connectedness of $\varGamma ({\mathbf {M}})$, it follows that $\phi$ fixes all directed edges and hence is the identity as a graph isomorphism. This means $\phi = {{\text {Id}}}$.$\square$

As a direct corollary, any orientation-preserving automorphism of a map is uniquely determined by the image of a single directed edge. Similarly, any automorphism of a map is uniquely determined by the combination of its orientation and the image of a single directed edge.

Regular maps have many other nice properties. For example, any face has the same number of edges, and any vertex has the same number of edges. Moreover, if a face f of a regular map ${\mathbf {M}}$ has p edges, and if we label the edges in counterclockwise order as $e_1,\ldots ,e_p$, then there is a unique orientation-preserving automorphism of ${\mathbf {M}}$ mapping $e_1$ to $e_2$. It fixes f by necessity. We can see it as a counterclockwise rotation around f of minimal degree.

Likewise, if a vertex v of ${\mathbf {M}}$ has q edges, we can define a counterclockwise rotation around v of minimal degree. More details on these constructions can be found for example in [6].

Notation 2.5

Let ${\mathbf {M}}$ be a regular map. Let f be a face of ${\mathbf {M}}$ with counterclockwise orientation. We always use the letter p to denote the number of edges of f, and we denote the counterclockwise rotation around f of minimal degree as described above by ${R}_f$.

Similarly, given a vertex v of ${\mathbf {M}}$, we always use the letter q to denote the number of edges of v. We write ${S}_v$ for the counterclockwise rotation around v of minimal degree.

We observe that ${R}_f$ has order p, and that any orientation-preserving automorphism of ${\mathbf {M}}$ fixing f is a power of ${R}_f$. Likewise, ${S}_v$ has order q, and any orientation-preserving automorphism of ${\mathbf {M}}$ fixing v is a power of ${S}_v$.

Let ${\mathbf {M}}$ be a reflexive regular map, and let e be an edge of ${\mathbf {M}}$. It can be shown that there are two orientation-reversing automorphisms that fix e as a non-directed edge. We will call these reflections. A visualization of rotations and reflections can be seen in Fig. 1.

Fig. 1

Rotations and reflections. An indication of the action is given by curved arrows in the left and middle figure (rotations), and by the two-way arrows in the right figure (reflection)

As an example, suppose v and w are adjacent vertices, and after fixing an orientation, let f be the face to the left of the oriented edge $\overrightarrow{(v,w)}$. The rotation ${S}_v$ around v maps $\overrightarrow{(v,w)}$ to $\overrightarrow{(v,{S}_v(w))}$, and the rotation ${R}_f$ around f maps the latter to $\overrightarrow{(w,v)}$. This means the automorphism ${R}_f\circ {S}_v$ inverts the oriented edge $\overrightarrow{(v,w)}$. As a consequence, it has order 2. In particular, for any regular map ${\mathbf {M}}$, if f is a face adjacent to a vertex v, then $({R}_f\circ {S}_v)^2 = {{\text {Id}}}$.

Lemma 2.6

Let ${\mathbf {M}}$ be a regular map, let v be a vertex of ${\mathbf {M}}$, and let f be a face of ${\mathbf {M}}$ incident to v. Then ${S}_v$ and ${R}_f$ generate ${{\text {Aut}}^+({{\mathbf {M}}})}$.

This lemma can be proved by showing that ${S}_v$ and ${R}_f$ can map a given directed edge to any other directed edge. A proof can be found in [5, Lem. 1.1.6]. For convenience, when we have $v \in {\mathrm {V}}({\mathbf {M}})$ and f a face of ${\mathbf {M}}$ incident to v, we occasionally use ${S}$ and ${R}$ instead of ${S}_v$ and ${R}_f$. An important consequence of the lemma is that we can pin down a regular map ${\mathbf {M}}$ without explicitly talking about its topology. We can give a presentation of ${{\text {Aut}}^+({{\mathbf {M}}})}$ in the generator pair $({R},{S})$. We call this a standard map presentation of ${\mathbf {M}}$.

Example 2.7

We have $|{{\text {Aut}}^+({\mathbf {T}})}| = 12$, where $\mathbf {T}$ denotes the tetrahedral map. Both the number of edges incident to a vertex and the number of edges incident to a face are 3. This means $q = 3$ and $p = 3$. Let $v \in {\mathrm {V}}(\mathbf {T})$ and f be a face incident to v. We find the obvious relations ${S}^3 = {{\text {Id}}}$ and ${R}^3 = {{\text {Id}}}$. Moreover, we have the relation $({S}{R})^2 = 1$, from the fact that ${S}{R}$ reverses the edge $(v,{R}^{-1}(v))$. It turns these are the only relators necessary to define a standard map presentation: ${{\text {Aut}}^+({\mathbf {T}})} = \langle {R}, {S}\mid {R}^3, {S}^3, ({R}{S})^2 \rangle$.

Remark 2.8

The isomorphism type of ${{\text {Aut}}^+({{\mathbf {M}}})}$ is insufficient to determine a regular map ${\mathbf {M}}$. Using ${\mathbf {R}_{{g.n}}}$ to denote the nth map in genus g according to the listing from [2], here are a few examples of regular maps with the same group of orientation-preserving automorphisms. To start with, the regular maps ${\mathbf {R}_{{3.1}}}$ and ${\mathbf {R}_{{10.9}}}$ both have ${{\text {Aut}}^+({{\mathbf {M}}})} \cong \text {PSL}(2,7)$. Even fixing the triple $({{\text {Aut}}^+({{\mathbf {M}}})},p,q)$, and thereby also the genus, does not necessarily determine a unique regular map. The counterexamples, tuplets, are of special interest (a different story altogether). The first examples occur in genus 8 (the twins ${\mathbf {R}_{{8.1}}}$ and ${\mathbf {R}_{{8.2}}}$) and genus 14 (the first Hurwitz triplet, ${\mathbf {R}_{{14.1}}}$, ${\mathbf {R}_{{14.2}}}$, ${\mathbf {R}_{{14.3}}}$). A regular map is, however, completely determined by a standard map presentation, as is treated in [6].

Proposition 2.9

There is a categorical equivalence between regular maps ${\mathbf {M}}$ as cell complexes with cellular maps, and group presentations of the form $\langle {R}, {S}\mid {{R}}^p, {{S}}^q, ({R}{S})^2, r_1,\ldots ,r_n \rangle$, the $r_k$ being extra relators. The morphisms of the second are group homomorphisms that respect the conjugacy classes of R and S in two such presentations.

A small theory of ${{\text {Aut}}^+({{\mathbf {M}}})}$-equivariant cellular morphisms between regular maps can be developed, as described in [5, Sect. 1.6]. The notion happily coincides with taking certain quotients of ${{\text {Aut}}^+({{\mathbf {M}}})}$, and a result we will use later in Lemma 3.14 and Proposition 3.15 is the following.

Proposition 2.10

  Suppose ${\mathbf {M}}$ is a regular map and H a normal subgroup of ${{\text {Aut}}({{\mathbf {M}}})}$ that is contained in ${{\text {Aut}}^+({{\mathbf {M}}})}$ and does not contain an automorphism that reverses some edge of ${\mathbf {M}}$. Then ${{\text {Aut}}({{\mathbf {M}}})}/H$ is the automorphism group of a regular map $\overline{{\mathbf {M}}}$ satisfying $\varGamma (\overline{{\mathbf {M}}}) = \varGamma ({\mathbf {M}})/H$ and ${\mathrm {F}}(\overline{{\mathbf {M}}}) = {\mathrm {F}}({\mathbf {M}})/H$. There is a branched cellular covering ${\mathbf {M}}\rightarrow \overline{{\mathbf {M}}}$ with the fiber of a cell of $\overline{{\mathbf {M}}}$ a coset of H. Each cell of ${\mathbf {M}}$ contains at most one ramification point, and each cell of $\overline{{\mathbf {M}}}$ contains at most one branch point. These numbers only depend on the dimension of the cell.

Here, by $\varGamma ({\mathbf {M}})/H$ we mean the graph obtained by identifying vertices respectively edges of $\varGamma ({\mathbf {M}})$ if they lie in the same H-orbit, and by ${\mathrm {F}}({\mathbf {M}})/H$ we mean the set obtained by identifying faces of ${\mathrm {F}}({\mathbf {M}})$ if they lie in the same H-orbit. The proposition follows from the work of [6]. A detailed proof can be found in [5].

Example 2.11

(Fermat maps) For $n \in \mathbb {Z}_{>0}$, let

$$\begin{aligned} G_n = \langle {R},{S}\mid {R}^3, {S}^{2n}, ({R}{S})^2, [{R},{S}]^3 \rangle . \end{aligned}$$

For each n, the group $G_n$ is the group of orientation-preserving automorphisms of a regular map that we call the Fermat map $\mathbf{Fer}(n)$, obtained by considering the solutions of $x^n+y^n+z^n = 0$, acted upon by its algebraic automorphism group. We omit the proof for this claim, but we do note that $\mathbf{Fer}(n)$ is a reflexive regular map, and that this is a remarkable property. The group structure can be described as $G_n \cong {\mathbb Z}_n^2 \rtimes \text {Sym}_3$. The graph $\varGamma (\mathbf{Fer}(n))$ is the full tripartite simple graph $K_{n,n,n}$ on 3n vertices. And since ${R}$ has order 3, the map is a triangular embedding of $K_{n,n,n}$. Its genus turns out to be ${n-1 \atopwithdelims ()2}$. A visualization of the first Fermat maps can be seen in Fig. 2.

Fig. 2

The first Fermat maps ($n=1,2,3,4$). The visualisation of $\mathbf{Fer}(4)$ was constructed in 1987 by Ulrich Brehm [1]

Definition 2.12

Let ${\mathbf {M}}$ be a regular map and let $v,v' \in {\mathrm {V}}({\mathbf {M}})$. Then the distance between v and $v'$ is the minimal length of a path in $\varGamma ({\mathbf {M}})$ from v to $v'$; it is denoted by $\mathrm {d}({v},{v'})$. The set of vertices at distance at most i from v is denoted $\mathrm {D}({v},{i})$. The set of vertices at distance precisely i from v is denoted by $\partial \mathrm {D}({v},{i})$.

The density ${\delta }({\mathbf {M}})$ of ${\mathbf {M}}$, which is the central notion for the rest of this paper, is defined as

$$\begin{aligned} {\delta }({\mathbf {M}}) := \frac{|\partial \mathrm {D}({v},{1})|}{|{\mathrm {V}}({\mathbf {M}})|} . \end{aligned}$$

Note that ${\delta }({\mathbf {M}})$ does not depend on the choice of v by the regularity of the map.

We will focus mainly on regular maps with simple graphs, in which case the density of the graph is simply the vertex-degree of any vertex divided by the total number of vertices. However, any regular map is a cellular cover of a map with simple graph, and the latter has the same density as the original map. Thus, while our main theorem only mentions reflexive regular maps with simple graph, it pins down the possibilities for density larger than $\frac{1}{2}$ to cellular covers of the tetrahedral map and Fermat maps.

Example 2.13

The Fermat maps all have density $\frac{2}{3}$. The tetrahedral map has density $\frac{3}{4}$.

Observe that if ${\mathbf {R}}$ is a regular map with simple underlying graph, then stating ${\mathbf {R}}$ has density strictly exceeding $\frac{1}{2}$ is the same as stating that ${\mathbf {R}}$ has v vertices and degree strictly exceeding $\frac{v}{2}$. In order to prove our regular map density Theorem 1.1, we will proceed to show that the Fermat maps and the tetrahedral map are the only reflexive regular maps with simple graph of density strictly exceeding $\frac{1}{2}$.

3 The Regular Map Density Theorem

Let ${\mathbf {R}}$ be a regular map. Let us write ${\mathrm {V}}= {\mathrm {V}}({\mathbf {R}})$ for convenience. We start with a rather technical but crucial lemma:

Lemma 3.1

Let $v,v' \in {\mathrm {V}}$. Suppose we have $j \in {\mathbb Z}$ such that ${S}_{v}^j$ fixes $v'$. Then the following claims hold.

• 1. There is $k \in {\mathbb Z}$ such that ${S}_{v}^j = {S}_{v'}^{kj}$. Moreover, k is well-defined and invertible modulo $\frac{q}{\gcd (j,q)}$.

• 2. Let ${g}\in {{\text {Aut}}({{\mathbf {R}}})}$. Suppose ${S}_{v}^j = {S}_{v'}^{kj}$. Then ${S}_{{g}(v)}^j = {S}_{{g}(v')}^{kj}$. Moreover, ${S}_{v}^j$ fixes ${g}(v)$ if and only if it fixes ${g}(v')$ and in this case, if ${S}_{v}^j = {S}_{{g}(v)}^{l}$, then ${S}_{v}^j = {S}_{{g}(v')}^{kl}$.

• 3. Let $k \in {\mathbb Z}$ be such that ${S}_{v}^j = {S}_{v'}^{kj}$. For all $i \in {\mathbb Z}$, we have ${S}_{v}^j = {S}_{{S}_{v}^i(v')}^{kj}$ and ${S}_{v}^j = {S}_{{S}_{v'}^i(v)}^j$.

• 4. Let ${g}_1,\ldots ,{g}_n \in {{\text {Aut}}({{\mathbf {R}}})}$ and suppose there is $v_i \in {\mathrm {V}}$ such that ${S}_{v}^j$ fixes both $v_i$ and ${g}_i(v_i)$ for all $i \in \{1,2,\ldots ,n\}$. Then ${S}_{v}^j$ fixes ${g}_n{g}_{n-1}\ldots {g}_1(v')$.

Proof

For Claim $\mathbf {1}$, note that any orientation-preserving element that fixes $v'$ is a rotation around $v'$, say ${S}_{v}^j = {S}_{v'}^i$. The order of these rotations must be equal, and in this case is equal to the smallest positive integer x such that $xj \equiv 0\mod q$, which is $\frac{q}{\gcd (j,q)}$, using the fact that $({S}_{v}^j)^x = 1$ precisely if xj is a multiple of q. Analogously, we observe that the order of these rotations must be equal to $\frac{q}{\gcd (i,q)}$, meaning $\gcd (i,q) = \gcd (j,q)$. In particular, both i and j are integer multiples of $\gcd (j,q)$, and moreover, these multiples must be invertible modulo $\frac{q}{\gcd (j,q)}$ (if not, the order of i or j modulo q would be strictly smaller than $\frac{q}{\gcd (j,q)}$). Clearly, there exists k, well-defined and invertible modulo $\frac{q}{\gcd (j,q)}$, such that $jk \equiv i$ mod q. This shows Claim $\mathbf {1}$.

For Claim $\mathbf {2}$, we have the equalities ${S}_{{g}(v)}^{j} = {g}{S}_{v}^{\pm j}{g}^{-1} = {g}{S}_{v'}^{\pm kj}{g}^{-1} = {S}_{{g}(v')}^{kj}$, where the sign in the exponent corresponds to the orientation of ${g}$ being positive or negative. If ${S}_{v}^j$ fixes ${g}(v)$ respectively ${g}(v')$, it is a power of ${S}_{{g}(v)}^j$ respectively ${S}_{{g}(v')}^j$ (which is itself a power of ${S}_{{g}(v)}^j$). In either case, ${S}_{v}^j$ fixes both ${g}(v)$ and ${g}(v')$. Moreover, if ${S}_{v}^j = {S}_{{g}(v)}^l$, we have ${S}_{v}^j = {S}_{{g}(v')}^{kl}$. This completes the proof of Claim $\mathbf {2}$.

The equality ${S}_{v}^j = {S}_{{S}_{v}^i(v')}^{kj}$ is easily seen because of Claim $\mathbf {2}$, using ${g}= {S}_{v}^i$. The equality ${S}_{v}^j = {S}_{{S}_{v'}^i(v)}^j$ follows by symmetry. This shows Claim $\mathbf {3}$.

To prove Claim $\mathbf {4}$, note that by Claim $\mathbf {2}$, we have ${S}_v^j$ fixes ${g}_1(v')$ if and only if it fixes ${g}_1(v)$. Exchanging the roles of $v'$ and $v_1$, we have ${S}_v^j$ fixes ${g}_1(v)$ if and only if it fixes ${g}_1(v_1)$. The latter is true by assumption, so ${S}_v^j$ fixes ${g}_1(v')$. Claim $\mathbf {4}$ now follows by induction. $\square$

While we formulated the previous lemma rather technically, the statements should be seen in a more geometrical and intuitive way. Any rotation ${S}_{v_0}^j$ that fixes a vertex $v_1$ must be a rotation around $v_1$ of the same order (Claim 1). Moreover, such a situation translates well under conjugation (Claims 2 and 3). Finally, the set of fixed points of an orientation-preserving automorphism ${S}_v^j$ is closed under the set of automorphisms ${g}'$ that map at least one fixed point of ${g}$ to another fixed point of ${g}$ (Claim 4). We will use this lemma often.

From here on, we will work under the following assumption.

Assumption 3.2

${\mathbf {R}}$ is a reflexive regular map with a simple graph.

An easy graph lemma gives us a point of departure to say something about regular maps with high density.

Lemma 3.3

If $\varGamma ({\mathbf {R}})$ has density ${\delta }({\mathbf {R}}) \ge \frac{1}{2}$, then $\varGamma ({\mathbf {R}})$ has diameter at most 2.

Proof

Let $v_0,v_1 \in {\mathrm {V}}$. Suppose that $\mathrm {d}({v_1},{v_0})\ge 2$. Then $\partial \mathrm {D}({v_0},{1})$ and $\partial \mathrm {D}({v_1},{1})$ are contained in $V - \{v_0,v_1\}$, which has cardinality $|V|-2$. Since we have $|\partial \mathrm {D}({v_0},{1})| + |\partial \mathrm {D}({v_1},{1})| \ge |V| > |V|-2$, we find that $v_0$ and $v_1$ share at least two common neighbors. In particular, this implies $\mathrm {d}({v_0},{v_1}) \le 2$. $\square$

In the following proposition, we will show that the faces of reflexive regular maps of high density are triangles ($p=3$).

Proposition 3.4

Suppose ${\delta }({\mathbf {R}}) > \frac{1}{2}$. Then $p=3$.

Proof

Let $v \in {\mathrm {V}}$ and let f be a face incident to v. Consider $v_1 ={R}_{f}^2(v)$ and suppose $v_1 \not \in \partial \mathrm {D}({v},{1})$. Then the same holds for ${S}_{v}^i(v_1)$ for any $i \in \{0,1,\ldots ,q-1\}$, because it preserves distances. In particular, the size of the orbit under $\langle {S}_v\rangle$ of $v_1$ is at most $|{\mathrm {V}}\setminus \partial \mathrm {D}({v},{1})|$. We have $|{\mathrm {V}}| < 2q$ because ${\delta }({\mathbf {R}}) > \frac{1}{2}$. Therefore, $|{\mathrm {V}}\setminus \partial \mathrm {D}({v},{1})| = |V|-q < 2q-q =q$. So the size of the orbit of $v_1$ under $\langle {S}_v\rangle$ is strictly smaller than q, and hence there is $j \in \{1,\ldots ,q-1\}$ satisfying ${S}_{v}^j(v_1) = v_1$.

Note that on one hand, ${S}_{v}^j$ does not fix any neighbor of v, and since ${\delta }({\mathbf {R}}) > \frac{1}{2}$, we find ${S}_{v}^j$ has at most $|V|-q < q$ fixed points. On the other hand, observe that for $v' = {R}_{f}(v)$, we have $v_1 = {S}_{v'}^{-1}(v)$. By Claim 4 of Lemma 3.1, using $g_i = {S}_{v'}^{-1}$, we find ${S}_{v}^j$ fixes ${S}_{v'}^i(v)$ for any i, so ${S}_{v}^j$ fixes all neighbors of $v'$, meaning it has at least q fixed points, a contradiction. We conclude $v_1 \in \partial \mathrm {D}({v},{1})$.

Label the neighbors of v by the elements of ${\mathbb Z}/q{\mathbb Z}$, counterclockwise and let $f_i$ be the face on the left of $\overrightarrow{(v,i)}$ (consistent with the orientation).

Suppose ${S}_{0}^{-1}(v) = i$. Since ${\mathbf {R}}$ is reflexive and the reflection that fixes the oriented edge $\overrightarrow{(v,0)}$ maps i to $-i$, we find ${S}_{0}(v)=-i$. Observe that this means that ${S}_{i}(v) = {S}_{v}^i{S}_{0}{S}_{v}^{-i}(v) = 0$. A visualization of the situation can be seen in Fig. 3. We now see two faces on the left of $\overrightarrow{(0,i)}$, being $f_0$ and $f_{i-1}$. We conclude $f_0 = f_{i-1}$. Since v occurs only once on each face (using the assumption that $\varGamma ({\mathbf {R}})$ is simple), we conclude $i=1$ and hence $p=3$, as was to be shown. $\square$

Definition 3.5

Assume we have a regular map with $p = 3$, and let $v \in {\mathrm {V}}$. A diagonal neighbor of v is an element of ${\mathrm {V}}$ of the form ${S}_{w}^2(v)$ with w a neighbor of v. Let $v' \in {\mathrm {V}}$ as well. We call v and $v'$ diagonally aligned if there is a sequence $(v_0,v_1,\ldots ,v_n)$ of elements of ${\mathrm {V}}$ satisfying $v_0 = v$, $v_n = v'$ and for all $i \in \{1,\ldots ,n\}$ the vertex $v_i$ is a diagonal neighbor of $v_{i-1}$.

If $v \in {\mathrm {V}}$ is a vertex of a triangle vwu, then wu is an edge of precisely one other triangle, say $wuv'$. In this case, $v'$ is a diagonal neighbor of v. All diagonal neighbors of v are of this form (Fig. 4).

Fig. 3

Proof of Proposition 3.4

Fig. 4

Diagonal neighbors and diagonal alignment

The observation that $v'$ is a diagonal neighbor of v if and only if v is a diagonal neighbor of $v'$ shows that being diagonally aligned is an equivalence relation. We write $v\sim v'$ if v and $v'$ are diagonally aligned. It is easy to see that being diagonally aligned is preserved by graph isomorphisms.

For $v \in {\mathrm {V}}$, we write ${\mathrm {V}}_v = \{v' \in {\mathrm {V}}: v' \sim v\}$. It is an easy exercise to see that if vwu is a face of $\varGamma ({\mathrm {V}})$, then any element of ${\mathrm {V}}$ is diagonally aligned to at least one of v, w or u (and in fact, either ${\mathrm {V}}_v$, ${\mathrm {V}}_w$ and ${\mathrm {V}}_u$ are pairwise disjoint or ${\mathrm {V}}_v = {\mathrm {V}}_w = {\mathrm {V}}_u = {\mathrm {V}}$).

Definition 3.6

Let ${\mathbf {R}}$ be a regular map. We define ${J}$ to be the minimal element of $\{1,2,\ldots ,q\}$ such that ${S}_v^{{J}}$ fixes all elements in ${\mathrm {V}}_v$. We call ${J}$ the primitive period of ${\mathbf {R}}$.

Note that ${J}$ exists because ${S}_v^q = {{\text {Id}}}$. Moreover, ${J}$ is independent of choice of v by Claim 2 of Lemma 3.1 (using the fact that $v \sim v'$ if and only if $g(v) \sim g(v')$ for all $v,v' \in {\mathrm {V}}$ and all $g \in {{\text {Aut}}({{\mathbf {R}}})}$), so we are justified in not using a subscript. Thirdly, ${J}$ divides q, since ${S}_v^q = {{\text {Id}}}$ fixes ${\mathrm {V}}_v$ pointwise.

Assumption 3.7

From this point on, we add to our previous assumptions (${\mathbf {R}}$ is a reflexive regular map with simple graph) that ${\mathbf {R}}$ satisfies ${\delta }({\mathbf {R}}) > \frac{1}{2}$. In particular, we will have $p = 3$ and $q \ge 2$.

Let $v \in {\mathrm {V}}$. The following lemma shows that we can classify ${\mathrm {V}}_v$ as the set of fixed points of ${S}_v^{{J}}$.

Lemma 3.8

Let $v \in {\mathrm {V}}$ and let $v'$ be a diagonal neighbor of v. Then the following claims hold.

• 1. The element ${J}$ is the minimal element in $\{1,\ldots ,q\}$ such that ${S}_v^{{J}}$ fixes $v'$.

• 2. We have ${J}= q$ if and only if $v' \in \partial \mathrm {D}({v},{1})$.

• 3. We have ${J}= q$ if and only if ${\mathrm {V}}_v = {\mathrm {V}}$.

• 4. If $w \in {\mathrm {V}}$ is fixed by ${S}_v^{{J}}$, then $w \in {\mathrm {V}}_v$.

• 5. If ${J}< q$, then ${\mathrm {V}}_v \cap \partial \mathrm {D}({v},{1}) = \emptyset$, q is even, and ${\delta }({\mathbf {R}}) \le \frac{2}{3}$.

• 6. If q is even, then ${J}< q$.

Proof

Claim $\mathbf {1}$ can be shown by induction. Suppose there is ${J}'$ such that ${S}_v^{{J}'}$ fixes $v'$. Then by Claim 3 of Lemma 3.1, it fixes any diagonal neighbor of v (since all of these are of the form ${S}_{v}^i(v')$), and analogously it fixes any diagonal neighbor of any diagonal neighbor of v, etcetera. Hence ${S}_v^{{J}'}$ fixes ${\mathrm {V}}_v$, and hence ${J}$ divides ${J}'$. Clearly, ${S}_v^{{J}}$ fixes $v'$, so this shows Claim $\mathbf {1}$.

For Claim $\mathbf {2}$, note that ${S}_v$ induces bijections on the sets $\{v\}$, $\partial \mathrm {D}({v},{1})$ and $\partial \mathrm {D}({v},{2})$. Note that $\partial \mathrm {D}({v},{1})$ has cardinality q and both $\{v\}$ and $\partial \mathrm {D}({v},{2})$ have cardinality less than q since ${\delta }({\mathbf {R}}) > \frac{1}{2}$. In particular, if $v' \not \in \partial \mathrm {D}({v},{1})$, its orbit under the powers of ${S}_v$ has cardinality strictly less than q, and hence ${J}< q$. Conversely, if $v' \in \partial \mathrm {D}({v},{1})$, then it is fixed by ${S}_v^{{J}}$, and therefore ${J}= q$.

For Claim $\mathbf {3}$, note that if ${\mathrm {V}}_v = {\mathrm {V}}$, then it contains a neighbor of v, and hence ${J}= q$. Conversely, if ${J}= q$, then $v'$ is a neighbor of v by the second part. Since ${\mathrm {V}}_v$ is the equivalence class of v under $\sim$, any rotation around v fixes it as a set. Hence all neighbors of v are elements of ${\mathrm {V}}_v$. But then $|{\mathrm {V}}_v| \ge q > \frac{1}{2}|{\mathrm {V}}|$, and hence ${\mathrm {V}}_v = {\mathrm {V}}$ (using the fact that either $|{\mathrm {V}}_v| = \frac{1}{3}|{\mathrm {V}}|$ or ${\mathrm {V}}_v = {\mathrm {V}}$).

For Claim $\mathbf {4}$, observe that if ${S}_v^{{J}}$ fixes w, then it also fixes ${\mathrm {V}}_w$. If ${\mathrm {V}}_w \ne {\mathrm {V}}_v$, then ${\mathrm {V}}_w$ contains a neighbor of v, and hence ${J}= q$. This gives a contradiction, since by Claim $\mathbf {3}$, ${\mathrm {V}}_v = {\mathrm {V}}$ and hence $w \in {\mathrm {V}}_v$.

For Claim $\mathbf {5}$, suppose ${J}< q$. If ${\mathrm {V}}_v \cap \partial \mathrm {D}({v},{1}) \ne \emptyset$, then ${S}_v^{{J}}$ fixes a neighbor of v, which gives a contradiction. So ${\mathrm {V}}_v \cap \partial \mathrm {D}({v},{1}) = \emptyset$.

Let w be a neighbor of v and consider the set $\bigl \{{S}_w^{2i}(v): i \in \bigl \{0,1,\ldots ,\bigl \lfloor \frac{q-1}{2}\bigr \rfloor \bigr \}\bigr \}$ of cardinality $1+\bigl \lfloor \frac{q-1}{2} \bigr \rfloor$. All of these elements lie in ${\mathrm {V}}_v$. If q is odd, then this set contains ${S}_w^{q-1}(v)$, which is a neighbor of v, a contradiction. Hence q is even, and this set has cardinality $\frac{q}{2}$. In particular, we find $|{\mathrm {V}}\setminus \partial \mathrm {D}({v},{1})| \ge \frac{q}{2}$, and hence ${\delta }({\mathbf {R}}) \le \frac{q}{q + q/2} = \frac{2}{3}$.

For Claim $\mathbf {6}$, suppose q is even and ${J}= q$. Then $v' \in \partial \mathrm {D}({v},{1})$. Let $w \in \partial \mathrm {D}({v},{1})$ such that $v' = {S}_w^2(v)$, and note that there is a directed edge $\overrightarrow{(w,{S}_w(v))}$. Consider the (unique) reflection that maps this edge to $\overrightarrow{({S}_w(v),w)}$. Since q is even, this reflection does not fix any neighbor of v. On the other hand, it fixes $v'$, a contradiction. $\square$

We can now show that the only reflexive regular map of density greater than $\frac{1}{2}$ with q odd is the tetrahedral map. After showing this, we can focus on the case where q is even.

Proposition 3.9

Suppose ${\delta }({\mathbf {R}}) > \frac{1}{2}$ and the vertex-degree q of ${\mathbf {R}}$ is odd. Then ${\mathbf {R}}$ is the tetrahedral map, and ${\delta }({\mathbf {R}}) = \frac{3}{4}$.

Proof

Let $v \in {\mathrm {V}}$. By Lemma 3.8, the primitive period ${J}$ of ${\mathbf {R}}$ is equal to q. Number the neighbors of v by $0,1,\ldots ,q-1$ clockwise and let $v' = {S}_{0}^2(v)$, a diagonal neighbor of v. It is a neighbor of v by the second part of Lemma 3.8.

Now, consider the reflection that maps that maps $\overrightarrow{(0,q-1)}$ to $\overrightarrow{(q-1,0)}$. It fixes v and $v'$. Moreover, it maps any neighbor i of v to $-i-1 \mod q$. We conclude $v' = \frac{q-1}{2}$.

Observe that we have a face $0,q-1,\frac{q-1}{2}$. Applying the rotation ${S}_{v}^{(q+1)/2}$ yields the triangle $\frac{q+1}{2},\frac{q-1}{2},0$. Because rotations preserve orientation, we conclude $\frac{q+1}{2} \equiv q-1 \mod q$. Since $q > 2$, we conclude $\frac{q+1}{2} = q-1$ and hence $q = 3$. We now easily deduce ${\mathbf {R}}$ is the tetrahedral map. $\square$

From the above proposition, we conclude the following. Every regular map ${\mathbf {R}}$ satisfying the conditions in Assumption 3.7 will either be the tetrahedral map, or have even vertex-degree q. In the latter case, we can say a few things about ${\mathbf {R}}$ using Claims 5 and 6 of Lemma 3.8.

Assumption 3.10

From here on, we’ll assume ${\mathbf {R}}$ is a reflexive regular map with simple graph satisfying ${\delta }({\mathbf {R}}) > \frac{1}{2}$ that is not equal to the tetrahedral map. In particular, we will have $p = 3$ and q is even. Moreover, we have ${J}< q$, ${\delta }({\mathbf {R}}) \le \frac{2}{3}$, and for all v, no neighbor of v is diagonally aligned to v.

Suppose vwu is a face of $\varGamma ({\mathbf {R}})$. Then ${S}_v$ maps ${\mathrm {V}}_w$ to ${\mathrm {V}}_u$ and vice versa. In particular, ${S}_v^2$ is a bijection of ${\mathrm {V}}_w$ and ${\mathrm {V}}_u$ (and of ${\mathrm {V}}_v$ of course). This motivates us to give the following definition:

Definition 3.11

Let ${j}:= \mathrm {lcm}({J},2)$. We call ${j}$ the even period of ${\mathbf {R}}$.

Lemma 3.12

For any $v,w \in {\mathrm {V}}$, we have $[{S}_v^{{j}},{S}_w^{{j}}] = {{\text {Id}}}$ and $[{S}_v^{{j}},{S}_w^{4}] = {{\text {Id}}}$.

Proof

If $v\sim w$, we have ${S}_v^{{j}}$ is a rotation around w, and hence it commutes with ${S}_w$, which implies both of the relations.

Suppose $v\not \sim w$. Note that ${S}_v^{{j}}$ fixes ${\mathrm {V}}_v$ pointwise and hence for any $v' \in {\mathrm {V}}_v$, we have $[{S}_v^{{j}},{S}_w^{{j}}](v') = {S}_v^{{j}}{S}_w^{{j}}{S}_v^{-{j}}{S}_w^{-{j}}(v') = {S}_w^{{j}}{S}_w^{-{j}}(v') = v'$, using the fact that ${S}_w^{{j}}$ fixes ${\mathrm {V}}_v$ as a set and ${S}_v^{{j}}$ fixes ${\mathrm {V}}_v$ pointwise. Likewise, $[{S}_v^{{j}},{S}_w^{{j}}]$ fixes ${\mathrm {V}}_w$ pointwise. There is $v' \in {\mathrm {V}}_v$ such that $v'$ is a neighbor of w. Now $[{S}_v^{{j}},{S}_w^{{j}}]$ fixes the edge $\overrightarrow{(v',w)}$ and hence it is ${{\text {Id}}}$.

Also, we have $[{S}_v^{{j}},{S}_w^{4}] = {S}_v^{{j}}{S}_{{S}_w^4(v)}^{-{j}}$. Let $v'' = {S}_w^2(v')$. We see that both $v'$ and ${S}_w^4(v')$ are diagonal neighbors of $v''$. There is k such that ${S}_{v'}^j = {S}_{v''}^{kj}$ by Claim 1 of Lemma 3.1. Note that k only depends on the fact that $v''$ is a diagonal neighbor of $v'$. This means that ${S}_{{S}_w^4(v')}^{{j}} = {S}_{v''}^{k{j}}$ as well, since $v''$ is a diagonal neighbor of ${S}_w^4(v')$. We conclude ${S}_{{S}_w^4(v')}^{{j}} = {S}_{v'}^{{j}}$ and hence $[{S}_{v'}^{{j}},{S}_w^{4}] = {{\text {Id}}}$. This implies $[{S}_{v}^{{j}},{S}_w^{4}] = {{\text {Id}}}$. $\square$

Let $v \in {\mathrm {V}}$ and let $v'$ be a diagonal neighbor of v. We have ${S}_{v}^{{j}} = {S}_{v'}^{k{j}}$ for some k, uniquely defined modulo $\frac{q}{{j}}$. By Claim 2 of Lemma 3.1, we find k is independent of choice of v and $v'$ (as long as they are diagonal neighbors). In particular, we find ${S}_{v'}^{{j}} = {S}_v^{k{j}}$ and hence $k^2 \equiv 1 \mod \frac{q}{{j}}$. We will show something stronger, namely the following.

Lemma 3.13

Let $v \in {\mathrm {V}}$ and let $v'$ be a diagonal neighbor of v. Then ${S}_v^{{j}} = {S}_{v'}^{{j}}$. Moreover, for any face vuw of $\varGamma ({\mathbf {R}})$, we have ${S}_v^{{j}}{S}_u^{{j}}{S}_w^{{j}} = {{\text {Id}}}$.

Proof

Let w be a neighbor of both v and $v'$ such that ${S}_w^2(v) = v'$. Label the neighbors of w counterclockwise with the elements of ${\mathbb Z}/q{\mathbb Z}$ with $v_0 = v$.

We have ${S}_{v_i}^{{j}} = {S}_{v_{i+4m}}^{{j}}$ for any $m \in {\mathbb Z}$ using the fact that ${S}_{v_i}^{{j}}$ commutes with ${S}_w^4$ by the previous lemma.

Note that ${\mathrm {V}}_v \cap \partial \mathrm {D}({w},{1}) = \{v_{2m}: m \in {\mathbb Z}\}$ and ${\mathrm {V}}_{v_1} \cap \partial \mathrm {D}({w},{1}) = \{v_{2m+1}: m \in {\mathbb Z}\}$. We claim that ${S}_v^{{j}}$ fixes ${\mathrm {V}}_{v_1} \cap \partial \mathrm {D}({w},{1})$ as a set. Note that it fixes ${\mathrm {V}}_{v_1}$ as a set since ${j}$ is even.

Suppose ${S}_{v_0}^{{j}}(v_i)$ is not a neighbor of w for some i. Then also ${S}_{v_{4m}}^{{j}}(v_{i+4m})$ is not a neighbor of w (because ${S}_{v_{4m}}^{{j}}(v_{i+4m})$ is simply ${S}_w^{4m}({S}_{v_0}^{{j}}(v_i))$, and rotations around w preserve distance to w). Since ${S}_{v_{4m}}^{{j}} = {S}_v^{{j}}$, we find that ${S}_{v_0}^{{j}}(v_{i+4m})$ is not a neighbor of w for any m. This means there are at least $\frac{q}{4}$ distinct elements in ${\mathrm {V}}_{v_i}$ at distance 2 of w. Moreover, there are $\frac{q}{2}$ distinct elements in ${\mathrm {V}}_{v_i}$ at distance 1 of w. Hence we find $|{\mathrm {V}}_{v_i}| \ge \frac{q}{2} + \frac{q}{4} = \frac{3}{4}q> \frac{3}{8}|{\mathrm {V}}| > \frac{1}{3} |{\mathrm {V}}| = |{\mathrm {V}}_{v_i}|$, which gives a contradiction. This shows that ${S}_v^{{j}}$ fixes ${\mathrm {V}}_{v_i} \cap \partial \mathrm {D}({w},{1})$ as a set for all i.

Suppose ${S}_{v}^{{j}}(v_1) = v_{1+{j}_1}$ and ${S}_v^{{j}}(v_{-1}) = v_{-1+{j}_{-1}}$. Note that ${S}_v^{{j}}(v_{\pm 1 + 4m}) = v_{\pm 1+4m+{j}_{\pm 1}}$, using ${S}_v^{{j}} = {S}_w^{4m}{S}_v^{{j}}{S}_w^{-4m}$.

Observe that ${S}_w^{-{j}_1}{S}_{v}^{{j}}$ fixes $v_1$, hence it is equal to ${S}_{v_1}^x$ for some x. Consider the reflection $\sigma$ that maps $\overrightarrow{(v,w)}$ to $\overrightarrow{(w,v)}$. It fixes $v_1$. Conjugating the equality ${S}_w^{-{j}_1}{S}_{v}^{{j}} = {S}_{v_1}^x$ with $\sigma$ gives ${S}_v^{{j}_1}{S}_{w}^{-{j}} = {S}_{v_1}^{-x}$. Together, these give the equality ${S}_w^{-{j}_1}{S}_{v}^{{j}}{S}_v^{{j}_1}{S}_{w}^{-{j}} = {{\text {Id}}}$, or in other words, ${S}_v^{{j}+{j}_1} = {S}_w^{{j}_1+{j}}$. This means that the rotation ${S}_v^{{j}+{j}_1}$ fixes w, which is a neighbor of v, and hence it is ${{\text {Id}}}$. We conclude ${j}_1 = -{j}$ modulo q. Analogously, we can show ${j}_{-1} = -{j}$ modulo q, so we find ${S}_v^{{j}}(v_{2m+1}) = v_{2m+1-{j}}$ for all m.

Repeating this argument for ${S}_{v'}^{{j}}$, we find ${S}_{v'}^{{j}}(v_{2m+3}) = v_{2m+3-{j}}$ for all m. This means ${S}_v^{{j}} = {S}_{v'}^{{j}}$, as both of these fix v and map $v_1$ to $v_{1-{j}}$. This shows the first part of the lemma.

For the second part, let $u = v_1$ and note that the equality ${S}_w^{-{j}_1}{S}_{v}^{{j}} = {S}_{v_1}^x$ is simply the equality ${S}_w^{{j}}{S}_{v}^{{j}} = {S}_{u}^x$. Conjugating with the rotation around vuw that maps v to u yields ${S}_v^{{j}}{S}_u^{{j}} = {S}_w^x$. Together, these equations give ${S}_w^{{j}}{S}_{w}^x{S}_u^{-{j}} = {S}_u^x$, and hence ${S}_w^{{j}+x} = {S}_u^{{j}+x}$. We conclude $x = -{j}$ modulo q as before, and hence ${S}_w^{{j}}{S}_{v}^{{j}} = {S}_u^{-{j}}$. From here, we easily find ${S}_v^{{j}}{S}_u^{{j}}{S}_w^{{j}} = {{\text {Id}}}$, as was to be shown. $\square$

Lemma 3.14

Suppose ${j}= q$. Then ${\mathbf {R}}= \mathbf{Fer}(1)$.

Proof

We have ${J}< q$ because ${\mathbf {R}}$ is not the tetrahedral map. Hence we have ${J}= \frac{q}{2}$ and ${J}$ is odd. For all $v,v' \in {\mathrm {V}}$, we have ${S}_{v'}^2(v) \in {\mathrm {V}}_v$, and hence ${S}_{v'}^2{S}_{v}^{{J}}{S}_{v'}^{-2}$ is a rotation of order 2 that fixes v, and hence it is ${S}_{v}^{{J}}$. This means that $[{S}_v^{{J}},{S}_{v'}^{2}] = {{\text {Id}}}$ for all $v,v' \in {\mathrm {V}}$. Let $v,w \in {\mathrm {V}}$ be neighbors and consider $H = \langle {S}_v^{{J}},{S}_w^{{J}} \rangle$. Let $u = {S}_v^{{J}}(w)$; note that $u\not \in {\mathrm {V}}_v\cup {\mathrm {V}}_w$. Now ${S}_v^{{J}}$ maps ${\mathrm {V}}_w$ to ${\mathrm {V}}_u$ and vice versa. Likewise, ${S}_w^{{J}}$ maps ${\mathrm {V}}_v$ to ${\mathrm {V}}_u$ and vice versa.

It is easily verified that ${S}_v^{{J}}{S}_w^{{J}}{S}_v^{{J}} = {S}_u^{{J}} = {S}_w^{{J}}{S}_v^{{J}}{S}_w^{{J}}$ (where the latter part follows from the fact that ${S}_u^{{J}} = {S}_{u'}^{{J}}$ for all $u' \in {\mathrm {V}}_u$). We now easily verify that $H \cong \mathrm {Sym}(3)$ and H is a normal subgroup of ${{\text {Aut}}({{\mathbf {R}}})}$ (any conjugation of ${S}_v^{{J}}$, ${S}_w^{{J}}$ is a rotation of order 2 around some vertex, and all such rotations are elements of H).

Observe that $|Hv| = 3$; this follows from the fact that |Hv| contains elements from ${\mathrm {V}}_v$, ${\mathrm {V}}_w$ and ${\mathrm {V}}_u$ and ${S}_v^{{J}}$ fixes v.

The argument now splits into two cases: either $Hv = \{v,w,u\}$ or $w,u\not \in Hv$. Assume the latter holds. Because $|Hv| = 3$ and $S_v^J(w)=u$, the orbit of the edge vw has size 6 and hence H reverses no edges; we may apply Proposition 2.10. This tells us that ${{\text {Aut}}({{\mathbf {R}}})}/H$ is the automorphism group of a reflexive regular map $\overline{{\mathbf {R}}}$ with $|{\mathrm {V}}(\overline{{\mathbf {R}}})| = \frac{|{\mathrm {V}}|}{3}$, $q(\overline{{\mathbf {R}}}) = \frac{q}{2}$ with simple graph. However, this means ${\delta }(\overline{{\mathbf {R}}}) = \frac{3}{2}{\delta }({\mathbf {R}}) > \frac{3}{4}$, which is not possible. We conclude that $Hv = \{v,w,u\}$.

Let $u' \in {\mathrm {V}}_u$ such that $vwu'$ is a face of ${\mathbf {R}}$ with ${S}_{u'}(v) = w$. Observe that ${S}_u^{{J}}$ interchanges v and w and hence the same is true for ${S}_{u'}^{{J}}$. We find ${S}_{u'}(\overrightarrow{(u',v)}) = \overrightarrow{(u',w)} = {S}_{u'}^{{J}}(\overrightarrow{(u',v)})$. It follows ${J}= 1$ and hence $q = 2$. Together with $p=3$, we immediately see ${\mathbf {R}}= \mathbf{Fer}(1)$. $\square$

With this lemma, the following proposition is now within our reach.

Proposition 3.15

Suppose $\frac{1}{2} < {\delta }({\mathbf {R}}) \le \frac{2}{3}$. Then ${\delta }({\mathbf {R}}) = \frac{2}{3}$.

Proof

We apply induction to the cardinality of ${\mathrm {V}}$. If ${\mathbf {R}}$ satisfies $|{\mathrm {V}}({\mathbf {R}})| \le 3$, then ${\mathbf {R}}$ has density $\frac{2}{3}$ simply because $\frac{2}{3}$ is the only possible fraction $\frac{n}{d}$ satisfying $\frac{1}{2} < \frac{n}{d} \le \frac{2}{3}$ and $d \le 3$. Suppose $|{\mathrm {V}}| > 3$ and assume the proposition is true for all ${\mathbf {R}}'$ with $|{\mathrm {V}}({\mathbf {R}}')| < |{\mathrm {V}}|$.

Consider $H = \langle {S}_v^{{j}},{S}_w^{{j}}\rangle$. Note that H is a subgroup of ${{\text {Aut}}({{\mathbf {R}}})}$ of order $\bigl (\frac{q}{{j}}\bigr )^2$, using Lemma 3.12 and the fact that ${S}_{v}^{x{j}}{S}_w^{y{j}} = {{\text {Id}}}$ if and only if both x and y are 0 mod $\frac{q}{j}$. Note that any conjugation of ${S}_v^{{j}}$ or ${S}_w^{{j}}$ is a rotation around some element of ${\mathrm {V}}$ of order $\frac{q}{{j}}$. In other words, any conjugation of these elements is of the form ${S}_u^{k{j}}$. If $u \in {\mathrm {V}}_v$ or $u\in {\mathrm {V}}_w$, this is an element of H by definition of ${j}$. If $u\not \in {\mathrm {V}}_v\cap {\mathrm {V}}_w$, we have ${S}_u^{k{j}} = {S}_v^{-k{j}}{S}_w^{-k{j}} \in H$ by Lemma 3.13. We conclude that H is normal in ${{\text {Aut}}({{\mathbf {R}}})}$. Moreover, H is generated by any pair ${S}_{v'}^{{j}},{S}_{w'}^{{j}}$ with ${\mathrm {V}}_{v'},{\mathrm {V}}_{w'}$ distinct.

By Proposition 2.10, ${{\text {Aut}}({{\mathbf {R}}})}/H$ corresponds to another regular map. Note that $|Hv| = \frac{q}{{j}}$ since ${S}_v^{{j}}$ fixes v and $|\langle {S}_w^{{j}} \rangle v| = \frac{q}{{j}}$. By the previous remark, $|Hv'| = \frac{q}{{j}}$ for all $v' \in {\mathrm {V}}$.

Moreover, if two edges $e,e'$ are incident to v, then $He = He'$ if and only if $e' = {S}_v^{k{j}}e$ for some $k \in {\mathbb Z}$.

Let $\overline{{\mathbf {R}}}$ be the regular map corresponding to ${{\text {Aut}}({{\mathbf {R}}})}/H$. By the above remarks, we have $|{\mathrm {V}}(\overline{{\mathbf {R}}})| = |{\mathrm {V}}|\frac{{j}}{q}$ and $q(\overline{{\mathbf {R}}}) = {j}$. Observe that $\overline{{\mathbf {R}}}$ has a simple graph. Indeed, suppose that two edges He, $He'$ in $\varGamma (\overline{{\mathbf {R}}})$ have the same vertices, say $Hv_1$ and $Hv_2$. Then in the original graph, we have $e = (v_1,v_2)$ and $e' = (v_1',v_2')$ with $Hv_1 = Hv_1'$ and $Hv_2 = Hv_2'$. Since $Hv_1 = Hv_1'$, we may assume $v_1' = v_1$ by picking another representative if necessary. Since there is an edge from $v_1$ to $v_2$, we have ${\mathrm {V}}_{v_1} \ne {\mathrm {V}}_{v_2}$, and hence we have $Hv_2 = \langle {S}_{v_1}^{{j}}\rangle v_2$. This means that $v_2' = {S}_{v_1}^{k{j}}(v_2)$ for some $k \in {\mathbb Z}$. Since $\varGamma ({\mathbf {R}})$ is simple, we conclude $e' = {S}_{v_1}^{k{j}}(e)$ as well, and hence $He = He'$.

We now find ${\delta }(\overline{{\mathbf {R}}}) = {\delta }({\mathbf {R}})$. Moreover, because we assumed $|{\mathrm {V}}| > 3$, we have ${\mathbf {R}}\ne \mathbf{Fer}(1)$ and hence ${j}\ne q$ by Lemma 3.14. This means $|{\mathrm {V}}(\overline{{\mathbf {R}}})| < |{\mathrm {V}}|$. By our induction hypotheses, we have ${\delta }({\mathbf {R}}) = {\delta }(\overline{{\mathbf {R}}}) = \frac{2}{3}$ as desired. This concludes the proof. $\square$

Corollary 3.16

If $\frac{1}{2} < {\delta }({\mathbf {R}}) \le \frac{2}{3}$ and $v,w,u \in {\mathrm {V}}$ with ${\mathrm {V}}= {\mathrm {V}}_v\cup {\mathrm {V}}_w\cup {\mathrm {V}}_u$, then $\partial \mathrm {D}({v},{1}) = {\mathrm {V}}_w\cup {\mathrm {V}}_u$.

Proof

We have $\partial \mathrm {D}({v},{1})\subseteq {\mathrm {V}}_w\cup {\mathrm {V}}_u$ by Lemma 3.8 (since ${\mathbf {R}}$ is not the tetrahedral map, hence ${J}< q$), and $|{\mathrm {V}}_w\cup {\mathrm {V}}_u| = \frac{2}{3}|{\mathrm {V}}|$. As $|\partial \mathrm {D}({v},{1})| = q = \frac{2}{3}|{\mathrm {V}}|$ by the previous lemma, the result must hold. $\square$

Proposition 3.17

Suppose ${\delta }({\mathbf {R}}) = \frac{2}{3}$. Then ${j}= 2$.

Proof

Let $v,w \in {\mathrm {V}}$ be neighbors. Label the neighbors of w by $0,1,\ldots ,q-1$ clockwise with $v = 0$. By our assumption on ${\delta }({\mathbf {R}})$, the elements of ${\mathrm {V}}_v$ are precisely elements of the form 2i mod q.

Let $u = {S}_v(w)$. Suppose ${S}_v(2i) = 2i'$. Then ${S}_v(2i+{j}) = {S}_v({S}_w^{{j}}(2i)) = {S}_u^{{j}}({S}_v(2i)) = {S}_u^{{j}}(2i') = 2i'-{j}$, using the fact that ${S}_u^{{j}}{S}_w^{{j}} = {S}_v^{-{j}}$ acts as the identity on ${\mathrm {V}}_v$. This means ${S}_v$ acts on congruence classes of 2i mod ${j}$. Moreover, we have ${S}_v(2+k{j}) = -(2+k{j})$ for any $k \in {\mathbb Z}$ because ${S}_v(2) = {S}_v({S}_w^2(v)) = {S}_w^{-2}(v) = -2$.

Let $\iota \in {\mathbb Z}_{>0}$ be minimal such that ${S}_v^{\iota }(2) \cong 2 \mod {j}$. Since the number of even congruence classes modulo j is $\frac{{j}}{2}$, we have $\iota \le \frac{{j}}{2}$. We now have ${S}_v^{\iota +1}(2) = -{S}_v^{\iota }(2)$. Let $\sigma$ be the reflection that fixes $\overrightarrow{(v,w)}$. It maps i to $-i$ and moreover, it maps ${S}_v^{\iota }(2)$ to ${S}_v^{-\iota +1}(2)$. In particular, we can conclude ${S}_v^{\iota +1}(2) = -{S}_v^{\iota }(2) = \sigma {S}_v^{\iota }(2) = {S}_v^{-\iota +1}(2)$. It follows ${S}_v^{2\iota }$ fixes 2 and hence it fixes ${\mathrm {V}}_v$ pointwise. This means ${J}| 2\iota$ and hence ${j}| 2\iota$. So $\iota \ge \frac{{j}}{2}$. This however means $\iota = \frac{{j}}{2}$. In particular, $2,{S}_v(2),\ldots ,{S}_v^{\iota -1}(2)$ are $\frac{{j}}{2}$ distinct even congruence classes modulo ${j}$, so it must be all of them.

Note however that ${S}_v$ fixes the congruence class 0 mod ${j}$. Since some power of ${S}_v$ maps 2 to an element that is 0 mod ${j}$, we see that 0 must the only even congruence class mod ${j}$. This is only possible if ${j}= 2$, as was to be shown. $\square$

We now restate and prove our main theorem.

Theorem 3.18

Suppose ${\mathbf {R}}$ is a regular map with simple graph satisfying ${\delta }({\mathbf {R}}) > \frac{1}{2}$. Then either ${\mathbf {R}}$ is chiral, or ${\mathbf {R}}$ is the tetrahedral map, or ${\mathbf {R}}= \mathbf{Fer}(n)$ for some $n \in {\mathbb Z}_{>0}$.

Proof

Suppose ${\mathbf {R}}$ is reflexive, and suppose ${\mathbf {R}}$ is not the tetrahedral map. We have $p=3$ by Proposition 3.4. By Lemma 3.8 and Proposition 3.9, we find q is even and ${\delta }({\mathbf {R}}) \le \frac{2}{3}$. Write $q = 2n$. By Lemma 3.15, we have ${\delta }({\mathbf {R}}) = \frac{2}{3}$ and by Proposition 3.17, we find ${j}= 2$.

Let $v \in {\mathrm {V}}$ and let w be a neighbor of v. Let f be the face on the left of $\overrightarrow{(v,w)}$. We claim that $[{S}_v,{R}_f]^3 = {{\text {Id}}}$.

Note that $[{S}_v,{R}_f] = {S}_v{S}_w^{-1}$. We have ${S}_v{S}_w^{-1}(v) = {S}_v^2(w)$. Note that ${S}_w^{-1}({S}_v^2(w)) = {S}_w({S}_v^2(w)) = {S}_v^{-2}(w)$ using the fact that ${S}_v^2(w) \in {\mathrm {V}}_w$. So $({S}_v{S}_w^{-1})^2(v) = {S}_v^{-1}(w)$. We have ${S}_v{S}_w^{-1}{S}_v^{-1}(w) = v$, showing $[{S}_v,{R}_f]^3 = ({S}_v{S}_w^{-1})^3$ fixes v.

On the other hand, we have $[{S}_v,{R}_f]^{-3} = ({S}_w{S}_v^{-1})^3$. By symmetry of the situation, it fixes w. But then $[{S}_v,{R}_f]^3$ also fixes w. This immediately implies $[{S}_v,{R}_f]^3 = {{\text {Id}}}$ as claimed.

It now follows that ${{\text {Aut}}^+({{\mathbf {R}}})}$ is a quotient group of $\langle {S},{R}\mid {S}^{2n}= {{\text {Id}}},{R}^3 = {{\text {Id}}},({S}{R})^2 = {{\text {Id}}},[{S},{R}]^3 = {{\text {Id}}}\rangle$ using ${S}= {S}_v$ and ${R}= {R}_f$. So ${{\text {Aut}}^+({{\mathbf {R}}})}$ is a quotient group of ${{\text {Aut}}^+({\mathbf{Fer}(n)})}$. On the other hand, we have $|{{\text {Aut}}^+({\mathbf{Fer}(n)})}| = 6n^2 = 3n\cdot 2n = |{\mathrm {V}}|\cdot q = |{{\text {Aut}}^+({{\mathbf {R}}})}|$. This means ${{\text {Aut}}^+({{\mathbf {R}}})} = {{\text {Aut}}^+({\mathbf{Fer}(n)})}$ and hence ${\mathbf {R}}= \mathbf{Fer}(n)$, as was to be shown. $\square$