Regular maps and hypermaps of Euler characteristic −1 to −200

Marston D.E. Conder^{∗}

Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand m.conder@auckland.ac.nz

November 15, 2007

Abstract This paper describes the determination of all orientably-regular maps and hypermaps of genus 2 to 101, and all non-orientable regular maps and hypermaps of genus 3 to 202. It extends the lists obtained by Conder and Dobcsányi (2001) of all such maps of Euler characteristic −1 to −28, and corrects errors made in those lists for the vertex- or face-multiplicities of 14 ‘cantankerous’ non-orientable regular maps. Also some discoveries are announced about the genus spectrum of orientably-regular but chiral maps, and the genus spectrum of orientably-regular maps having no multiple edges, made possible by observations of patterns in the extension of these lists to higher genera.

2000 Mathematics Subject Classification: 05C25, 57M15

1 Introduction

This brief paper has many purposes. The first is to announce an extension of the tables in [4] of all regular and orientably-regular maps of small genera. We describe the application of a greatly improved computational algorithm for finding all normal subgroups of up to a given index in a finitely-presented group, in order to determine of all orientably-regular maps and hypermaps of genus 2 to 101, and all non-orientable regular maps and hypermaps of genus 3 to 202. The second is to notify some corrections to the vertex- and face-multiplicities of the ‘cantankerous’ examples of nonorientable regular maps listed in [4]. Finally, we announce some discoveries about the genus spectrum of orientably-regular but chiral maps, and the genus spectrum of orientably-regular maps having no multiple edges, which were made possible by observations of patterns in the extension of the lists in [4] to higher genera.

∗Research supported in part by the N.Z. Marsden Fund, Grant UOA 412

2 Regular maps of small genus

An map is a 2-cell embedding of a finite connected graph or multigraph into a closed surface, and an automorphism of such a map is a permutation of the edges that preserves incidence with vertices and faces of the embedding. A map M is called regular if the group Aut(M) of all its automorphisms has a single orbit on incident vertex-edge-face triples. Such a map can be orientable or non-orientable, according to the nature of the supporting surface. An orientably-regular map is a map M on an orientable surface with the property that the group Aut^{o}(M) of all its orientationpreserving automorphisms has a single orbit on incident vertex-edge pairs, and if such a map admits also an orientation-reversing automorphism then the map is said to be reflexible, while otherwise it is chiral. If M is a regular or orientably-regular map, then the Euler characteristic and the genus of M are defined to be the same as those of the supporting surface, and the type of M is the pair {k, m}, where k is the size of each face of M and m is the degree/valence of each vertex of M. Note that if M has Euler characteristic χ, then its genus g is given by χ = 2 − 2g if M is orientable, or χ = 2 − g if M is non-orientable.

If M is regular of type {k, m} then Aut(M) is a homomorphic image of the (k, m, 2) triangle group Δ(k, m, 2) = ⟨ a, b, c | a^{2} = b^{2} = c^{2} = (ab)^{k} = (bc)^{m} = (ca)^{2} = 1 ⟩, with the images F, V and E of ⟨a, b⟩, ⟨b, c⟩ and ⟨a, c⟩ giving the stabilizers of a face, vertex and edge of M, respectively. Conversely, if K is any normal subgroup of finite index in Δ(k, m, 2) such that K intersects each of ⟨a, b⟩, ⟨b, c⟩ and ⟨a, c⟩ trivially, then Δ(k, m, 2)/K is the automorphism group of a regular map M of type {k, m}. A similar correspondence exists between orientably-regular maps of type {k, m} and normal subgroups of finite index in the index 2 subgroup Δ^{o}(k, m, 2) of Δ(k, m, 2) generated by R = ab and S = bc which intersect each of ⟨R⟩, ⟨S⟩ and ⟨RS⟩ trivially. The latter subgroup Δ^{o}(k, m, 2) has presentation ⟨ R, S | R^{k} = S^{m} = (RS)^{2} = 1 ⟩, and is sometimes known as the ordinary (k, m, 2) triangle group.

This correspondence between regular or orientably-regular maps and normal subgroups of finite index in triangle groups has been exploited to develop the theory of such maps and produce or classify many families of examples. In particular, it was used by Conder and Dobcsányi in [4] to determine all regular and orientablyregular maps of Euler characteristic −1 to −28 inclusive, through the application of an improvised method for finding all normal subgroups of up to a given index in a finitely-presented group. Complete lists were provided in [4] of all orientably-regular maps of genus 2 to 15 inclusive (with reflexible and chiral maps given separately) and all non-orientable regular maps of genus 3 to 30 inclusive.

Subsequently, Derek Holt suggested an alternative method for finding normal subgroups of finite index in a finitely-presented group, based on construction of a composition series for he quotient. This suggestion was taken up by his PhD student, David Firth, and reported in his PhD thesis [7] and has been implemented as a new procedure (called LowIndexNormalSubgroups) in the computational algebra system Magma [2]. This new method works for index up to 100, 000, and much faster than the one used for [4],

In August 2006 the author of this paper used the new procedure in Magma to determine all regular and orientably-regular maps of Euler characteristic −1 to −200 inclusive, again by exploiting the correspondence with normal subgroups of finite index in triangle groups (in the same way as explained in [4]. The resulting lists are available on the author’s website (see [3]), and provide the following:

• all reflexible orientably-regular maps of genus 2 to 101 inclusive,

• all chiral orientably-regular maps of genus 2 to 101 inclusive, and

• all non-orientable regular maps of genus 3 to 202 inclusive.

A big advantage of this recent work is that the new information reveals patterns in the genus spectrum of various kinds of maps never seen before.

For example, it shows that there is no orientably-regular but chiral map of genus 2, 3, 4, 5, 6, 9, 13, 23, 24, 30, 36, 47, 48, 54, 60, 66, 84 or 95. In fact, further computations with this observation in mind have shown that there is no such map of genus 108, 116, 120, 139, 150, 167, 168, 174, 180, 186 or 198. Now a lot of these exceptional genera are of the form p + 1 where p is prime. Moreover, the extended lists show that all orientably-regular but chiral maps of genus p + 1 for small prime p are of just three types: type {5, 10} for p ≡ 1 mod 10, type {6, 6} for p ≡ 1 mod 6, and has type {8, 8} for p ≡ 1 mod 8. This led the author to conjecture the following, subsequently proved in joint work with Jozef Širáň and Tom Tucker (see [5]):

Theorem 2.1 Suppose M is a orientably-regular but chiral map of genus p+1, where p is prime. Then p divides |Aut(M)|, and either M or its topological dual M^{∗} has type {5, 10} (with p ≡ 1 mod 10), type {6, 6} (with p ≡ 1 mod 6), or type {8, 8} (with p ≡ 1 mod 8). In particular, there is no orientably-regular but chiral map of genus p + 1 whenever p is a prime not congruent to 1 modulo 3, 5 or 8.

Similarly, there is no reflexible orientably-regular map of genus 20, 32, 38, 44, 62, 68, 74, 80 or 98 with simple underlying graph. In particular, the latter observation answers negatively a question a raised some years ago by David Surowski at the first SIGMAC conference (on symmetries of graphs, maps and complexes) at Flagstaff, Arizona, in 1998, by showing for the first time that some orientable surface carries no reflexible regular map with simple underlying graph. Again a lot of these exceptional genera are of the form p + 1 where p is prime, and joint work with Jozef Širáň and Tom Tucker has resulted in the following (see [5]):

Theorem 2.2 Suppose M is an orientably-regular map of genus p + 1, where p is prime. If M is chiral and p − 1 is not divisible by 5 or 8, or if M is reflexible and p > 13, then either M or M^{∗} has multiple edges. Moreover, if M is reflexible, p > 13 and p ≡ 1 mod 6, then both M and M^{∗} have multiple edges. In particular, there is no reflexible regular map M with simple underlying graph on an orientable surface of genus p + 1 whenever p is a prime congruent to 1 mod 6 and p > 13.

In fact, as a result of these observations, what is achieved in [5] is a complete classification of all regular or orientably-regular maps M for which |Aut M| is coprime to the Euler characteristic χ (if χ is odd) or to χ/2 (if χ is even). Aside from the two theorems above, this classification can also be used to give a simpler proof of the following, first obtained in [1]:

Theorem 2.3 Suppose M is a non-orientable regular map of characteristic −p, where p is prime and p > 13. Then up to duality, one of the following holds:

(a) p ≡ 3 mod 4, and M has type {2r, 2s}, for r, s odd and p = rs − s − r, or
(b) p ≡ 5 mod 6, and M has type {4, p + 4}.

In particular, if p > 13 and p ≡ 1 mod 12, then there exists no non-orientable regular map of characteristic −p.

3 Correction of errata in the multiplicities in the earlier list of non-orientable regular maps

In 14 of the 83 cases of non-orientable regular maps of genus 3 to 30 listed in Table 3 of [4], either the vertex- or face-multiplicity was given incorrectly. The reason for this error is that the corresponding maps are ‘cantankerous’, as defined by Steve Wilson in [9]. More specifically, in the computations reported in [4], the vertexor face-multiplicities were taken (respectively) as the orders of the normal cores of the vertex-stabilizing subgroup ⟨S⟩ = ⟨bc⟩ and face-stabilizing subgroup ⟨R⟩ = ⟨ab⟩ in the automorphism group of the map, but for cantankerous maps, these do not always give the multiplicities, because a relation of the form a(bc)^{m/2}a ∈ ⟨b, c⟩\⟨bc⟩ or c(ab)^{k/2}c ∈ ⟨a, b⟩\⟨ab⟩ is satisfied. This is a characterizing feature of cantankerous maps, and hence the multiplicities for all other maps in the tables in [4] are correct. The true multiplicities for the cantankerous maps in [4] are given in the table below. The correct multiplicities for these maps (and for all the cantankerous maps of higher genus) are also given in the new lists in [3].

Table 1: Cantankerous maps of genus 3 to 30

Map Genus Type Automs m_{V}  m_{F}  Additional relators
N4.1  4  {4, 6}  48  2  2 (not 1) R^{4}, T S^{−1}RS^{−1}R^{−2}, S^{6}
N5.2  5  {4, 6}  72 2 (not 1)  1  R^{4}, S^{6}, T (S^{−1}R)^{3}R^{−3}, T S^{−2}RS^{−3}R^{−1}
N7.2  7  {4, 9}  72  3  2 (not 1) R^{4}, T S^{−1}RS^{−1}R^{−2}, S^{9}
N10.3  10 {4, 12} 96  4  2 (not 1) R^{4}, T S^{−1}RS^{−1}R^{−2}, S^{12}
N12.3* 12 {6, 6} 120 2 (not 1) 2 (not 1) R^{6}, S^{6}, T S^{−1}R^{2}S^{−1}R^{−3}, T S^{−2}RS^{−3}R^{−1}
N13.1  13 {4, 15} 120  5  2 (not 1) R^{4}, T S^{−1}RS^{−1}R^{−2}, S^{15}
N16.4  16 {4, 18} 144  6  2 (not 1) R^{4}, T S^{−1}RS^{−1}R^{−2}, S^{18}
N17.2  17 {4, 10} 200 2 (not 1)  1  R^{4}, [RS, SR], S^{10}, T S^{−1}(RS^{−3})^{2}R^{−2}
N19.1  19 {4, 21} 168  7  2 (not 1) R^{4}, T S^{−1}RS^{−1}R^{−2}, S^{21}
N22.2  22 {4, 24} 192  8  2 (not 1) R^{4}, T S^{−1}RS^{−1}R^{−2}, S^{24}
N22.3  22 {6, 6} 240  1  2 (not 1) R^{6}, S^{6}, T S^{−1}R^{2}S^{−1}R^{−3}
N25.1  25 {4, 27} 216  9  2 (not 1) R^{4}, T S^{−1}RS^{−1}R^{−2}, S^{27}
N28.2  28 {4, 30} 240  10  2 (not 1) R^{4}, T S^{−1}RS^{−1}R^{−2}, S^{30}
N29.4  29 {6, 12} 216  3  2 (not 1) R^{6}, T S^{−1}R^{2}S^{−1}R^{−3}, (RS^{−3})^{2}

4 Regular hypermaps of small genus

A hypermap can be defined as a generalisation of a map on a surface, with edges replaced by ‘hyperedges’. The full automorphism group of a (reflexible) regular hypermap H of type {k, l, m} is a quotient of the (k, l, m) triangle group Δ(k, l, m) = ⟨ a, b, c | a^{2} = b^{2} = c^{2} = (ab)^{k} = (bc)^{l} = (ca)^{m} = 1 ⟩, with the images F, V and E of ⟨a, b⟩, ⟨b, c⟩ and ⟨a, c⟩ giving the stabilizers of a hyperface, hypervertex and hyperedge of H, respectively. Similarly, the orientation-preserving automorphism group of an orientably-regular hypermap H of type {k, l, m} is a quotient of the ordinary (k, l, m) triangle group Δ^{o}(k, l, m) = ⟨ x, y, z | x^{k} = y^{l} = z^{m} = xyz = 1 ⟩, which is isomorphic to the index 2 subgroup of Δ(k, l, m) generated by ab, bc and ca.

The theory of such objects is well-developed, and thoroughly explained in [6]. Also connections with Galois theory and Grothendieck’s programme are described in [8]. When one of the parameters k, l, m is 2, H is a map, and otherwise, if all of k, l, m are at least 3, then we will say H is proper. As with maps, an orientably-regular hypermap is either reflexible or chiral. Also regular and orientably-regular hypermaps can be regarded as equivalent under triality, corresponding to a permutation of the generators a, b, c or x, y, z of the associated triangle group (which then gives rise to a permutation of the parameters k, l, m determining the type).

Using the new LowIndexNormalSubgroups procedure in Magma [2]. the author of this paper has determined all regular and orientably-regular proper hypermaps of Euler characteristic −1 to −200 inclusive, again by exploiting the correspondence with normal subgroups of finite index in triangle groups. These computations provide lists (available from [3]) of the following, up to isomorphism and triality:

• all reflexible orientably-regular proper hypermaps of genus 2 to 101 inclusive,

• all chiral orientably-regular proper hypermaps of genus 2 to 101 inclusive, and • all non-orientable regular proper hypermaps of genus 3 to 202 inclusive.

References

[1] A.B. D’Azevedo, R. Nedela and J. Širáň, Classification of regular maps of negative prime Euler characteristic, Trans. Amer. Math. Soc. 357 (2005), 4175–4190.

[2] W. Bosma, J. Cannon and C. Playoust, The Magma Algebra System I: The User Language, J. Symbolic Computation 24 (1997), 235–265.

[3] M.D.E. Conder, Lists of rotary and regular maps and hypermaps of small genus,

    http://www.math.auckland.ac.nz/∼conder/hypermaps.html.

[4] M. Conder and P. Dobcsányi, Determination of all regular maps of small genus, J. Combin. Theory Ser. B 81 (2001), 224–242.

[5] M. Conder, J. Širáň and T. Tucker, The genera, reflexibility and simplicity of regular maps, preprint.

[6] D. Corn and D. Singerman, Regular hypermaps, European J. Combin. 9 (1988), 337–351.

[7] D. Firth, An algorithm to find normal subgroups of a fintiely presented group up to a given index, PhD Thesis, University of Warwick, 2005.

[8] G. A. Jones and D. Singerman, Belyĭ functions, hypermaps, and Galois groups, Bull. London Math. Soc. 28 (1996), 561–590.

[9] S. Wilson, Cantankerous maps and rotary embeddings of K_{n}, J. Combin. Theory Ser. B 47 (1989), 262–273.