Документ взят из кэша поисковой машины. Адрес оригинального документа : http://dfgm.math.msu.su/files/papers-sym/reg%20maps%20nonorientable%20surfaces.pdf Дата изменения: Wed Feb 27 20:08:20 2008 Дата индексирования: Sat Apr 9 22:58:50 2016 Кодировка: Поисковые слова: transit

Geometriae Dedicata 56: 209-219, 1995. © 1995 KluwerAcademic Publishers. Printed in the Netherlands.

209

Regular Maps on Non-orientable Surfaces
MARSTON CONDER and BRENT EVERITr
Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand

(Received: 12 April 1994; revised version: 20 June 1994)
Abstract. It is well known that regular maps exist on the projectiveplane but not on the Klein bottle,

nor the non-orientable surface of genus 3. In this paper several infinite families of regular maps are constructed to show that such maps exist on non-odentablesurfacesof over 77 per cent of all possible genera.
Mathematics Subject Classification (1991): 05C25.

1. Introduction

Regular maps may be thought of as a combinatorial generalization of the Platonic solids. The standard authority is the book by Coxeter and Moser [4], in which copious examples are provided of regular maps that lie on orientable surfaces. In fact, it is easy to construct a regular map on an orientable surface of any genus g>0. The situation where the map resides on a non-orientable surface is also considered briefly in [4]. It is easily shown how to obtain a regular map on the projective plane: just by identifying antipodal points of some of the Platonic solids for instance. Less obvious, however, is the non-existence of regular maps on the Klein bottle (genus 2) or on the non-orientable surface of genus 3. Despite this apparent evidence to the contrary, regular maps do exist on most non-orientable surfaces. (This statement will be clarified later.) Table 8 of [4] contains many examples, and in [6] Steve Wilson gives an infinite family of nonorientable surfaces that admit regular maps whose underlying graph is complete in each case. In this paper we describe a group-theoretic construction which we then use to show that regular maps exist on non-orientable surfaces of over 77 per cent of all possible genera. Our construction involves taking the semi-direct product of a cyclic group N (of variable order) by a fixed group//which is known to be the automoq~hism group of a non-ofientable regular map M with appropriate parameters; this is achieved in such a way that the resulting groups are the automorphism groups of a family of non-orientable maps which all have the given map M as a quotient.


210

MARSTON CONDER AND BRENT EVERITT

First we describe some of the standard background on regular maps in Section 2, including the connection with group presentations which is fundamental to our approach. Details of the construction and a family of starting blocks (that is, possibilities for the 'top' group//) are given in Section 3, and the genera obtained so far are summarized and discussed in Section 4.

2. Basic Concepts and the Groups

G p,q,r

A map is a 2-cell embedding of a connected graph into a closed surface without
boundary. Such a map M is thus composed of a vertex-set V, an edge-set E, and a set of faces which we will denote by F. The faces of M are of course the connected components of the space obtained by removing the embedded graph from the surface; alternatively, in the orientable case, they can be considered without recourse to geometry by considering just the underlying graph together with a 'rotation' at each vertex (see [1]). Associated also with any map is a set of darts, or arcs, which are the incident vertex-edge pairs (v, e) E V в E. Each dart is made up of two blades, one corresponding to each face containing the edge e (except in degenerate situations where an edge lies in just one face, but these will not concern us here). An automorphism of a map M is a permutation of its blades, preserving the properties of incidence, and as usual these form a group under composition, called the automorphism group of the map, and denoted by Aut(M). Now if the group Aut(M) contains elements R and S with the property that R cyclically permutes the consecutive edges of some face f (in single steps around f), and S cyclically permutes the consecutive edge incident to some vertex v of f (in single steps around v), then following Wilson [6] we call M a rotary map. In this case (by connectedness) the group Aut(M) acts transitively on the vertices, on edges, and on faces of M, and it follows that all the faces are bordered by the same number of edges, say p, while all the vertices have the same degree, say q. Notice also that the automorphism RS interchanges the vertex v with one of its neighbours along an edge e (on the border of f), interchanging f with the other face containing e in the process. The three automorphisms R, S and RS may thus be viewed as rotations which satisfy the relations R p--S q=(RS) 2-- 1. If a rotary map M admits also an automorphism a which (like RS) 'flips' the edge e but (unlike RS) preserves the face f, then we say the map M is regular. This automorphism a is essentially a reflection, about an axis passing through the midpoints of the edge e and the face f. Similarly, the automorphisms b = aR and e = bS may also be thought of as reflections, and the following relations are satisfied:

a 2=b 2=c 2=(ab) p=(bc) q=(ca) 2=1.


REGULAR MAPS ON NON-ORIENTABLE SURFACES

211

Note: In [4] rotaty maps are called regular, while regular maps are called reflexible;
this notation appears to have been abandoned. By connectedness, every automorphism is uniquely determined by its effect on any blade, and in particular, the stabilizer of every blade is trivial. In the case of a rotary map M, the group Aut(M) is transitive on darts, but if M is regular, then Aut(M) is transitive (indeed regular) on blades. As a consequence, the automorphism group of a regular map M is generated by the reflections a, b, e, described above. Counting the number of blades containing a given edge e yields IAut(M)l = 21E I when M is rotary but not regular, while IAut(M)l = 41E I when M is regular. In either case, counting the number of darts incident with a given vertex, edge or face gives the well-known identity qlVI = 21E [ = plFI. One other geometric notion we consider is that of a Petrie polygon: this is a 'zig zag' circuit in which every two but no three consecutive edges border the same face. It is not difficult to see that every edge of a map M lies in exactly two Petrie polygons, and so we can talk of the Petrie dual P(M) of M as that map which has the same vertices and edges as M but whose faces are the Petrie polygons of M. Note that P(M) is dual to M in the sense that it establishes a duality between faces and Petrie polygons: the Petrie polygons of P(M) are the faces of M, and vice-versa. Also, as with the standard dual D(M) (obtained by interchanging the roles of the vertices and faces), the Petrie dual P(M) is regular if and only if M is regular; see Wilson [5]. On the other hand, unlike the standard dual, the Petrie dual may lie on a different surface from that of the given map M, and in particular, P(M) can often be orientable when M is not. When M is regular, the automorphism abe acts like a glide reflection, moving some Petrie polygon along itself in consecutive steps. If the Petrie polygon contains r edges, then a, b and c satisfy the relations a 2 = 52 = c2 ---- (ab) p -- (bc) q -- (ca) 2 -- (abc) r = I (1)

and we say that M has parameters {p, q),. Note that D(M) then has parameters {q,p}~, while P(M) has parameters {r, q}p, and in fact all six permutations of {p, q, r} are possible; see [5]. The relations (1) are defining relations for the abstract group G p,q,r defined by Coxeter (see [3]). By what we have outlined above, the automorphism group of any regular map M of type {p, q}, is a non-degenerate homomorphic image of this group G p,q,~, 'non-degenerate' meaning that the orders of a, b and e and their products ab, bc and ca are preserved. Conversely, any non-degenerate homomorphism from G p,q,~ to a finite group G yields a regular map M with parameters {p, q}~ on which G acts as its automorphism group. In fact the vertices, edges and faces of M may be taken as the cosets in G of the (images of the) subgroups V = (b, c), E = (a, c) and F = (a, b) respectively, with G acting by right multiplication. (These three subgroups then


212

MARSTON CONDER AND BRENT EVERITT

become the stabilizers of some mutually incident vertex v, edge e and face f respectively.) Finally, note that the regular map M is orientable if and only if the subgroup (ab, bc) of G = Aut(M) has index 2 in G (as does its pre-image in the group GP,q,r). In this case (ab, bc) = (R, S) has two orbits on blades, with the two blades associated with any given dart lying in different orbits. The elements of this evenlength word subgroup are 'rotations', while all other elements of G are 'reflections' (or glide reflections), reversing the orientation of the surface. In the non-orientable case, however, the subgroup (ab, be) has index 1 in G. In particular, this subgroup has just one orbit on blades - as shown in [4] using a simple colouring argument- and there are no true reflections: every reflection is a product of rotations. The genus of M is defined as the genus g of the non-orientable surface on which M is embedded, and is given the usual formula in terms of the Euler characteristic: 2 - g = X = IYl- IEI + IFI. As 2plFI = 41EI = 2qlYl -- IGI, the latter formula simplifies to g = IGI(1/4 - 1/2p - 1/2q) + 2.

3. The Construction Using the correspondence between regular maps and generators for their automorphism groups (as described in the previous section), we can set about finding regular maps on non-orientable surfaces by constructing groups with the appropriate properties. Suppose H is a finite group generated by elements u, v and t which satisfy the relations u 2 = v q = (uv) p = t 2 -- (ut) 2 = (vt) 2 = 1, with v and uv having (true) orders p and q respectively, and such that uv and v 2 generate a subgroup of index 2 in H, containing t. In this case necessarily q is even, and H itself is generated by u and v. Also let N be a cyclic group of order n, generated by some element w. Now form the semi-direct product (or split extension) NH of N by H, with H acting on N by conjugation in such a way that u and v both invert w, this is: u-lwu = W -1 = v-lwv. In this group define a = wut, b = tv and c = t, and consider the subgroup G generated by a, b and c. Note that w is centralized by both uv and v 2, and therefore also by t. In particular, this implies a 2 = (wut) 2 = ww-l(ut) 2 = 1, so that a has order 2. Similarly b, c and ca all have order 2, while bc = v -1 has order q. Next ab = wut2v = wuv and therefore (ab) p = w p, hence the order of ab is equal to lcm(n, p). It follows that G is the automorphism group of some regular map M whose vertices all have degree q and whose faces are all bounded by lcm(n, p) edges. The numbers of vertices, edges and faces of M depend on the order of G, and its orientability (or otherwise) depends on whether or not the subgroup generated by ab, bc and ca has index 2 (or 1). To see what can happen, we consider a few examples:


REGULAR MAPS ON NON-ORIENTABLE SURFACES

213

EXAMPLE 3.1. Let H be the symmetric group $4, and in this group let u = ( 1, 2), v = ( 1, 2, 3, 4) and t = ( 1,2)(3, 4). Note that u and v themselves generate $4, and that t = (uv)-lv2uv; in fact that subgroup generated by uv = (1, 3, 4) and v 2 = (1, 3)(2, 4) is the alternating group A4, which obviously contains t, so the above conditions are satisfied. Now if w has order n, then ab has order n if n is divisible by 3, and 3n otherwise. Also since u 2 = v 4 = (uv) 3 = 1 are defining relations for the group H = $4, it follows that G = (a, b, c) has order 24 times the order of w 3, that is: IGI = 8n if n is divisible by 3, while IGI = 24n if n is not. Further, as (ab)-l(cb)2ab = (wuv)-lv2wuv = (uv)-lv2uv -- t = c we find c lies in the rotation subgroup (ab, bc), which therefore has index 1 in G. It follows that the corresponding map is non-orientable. By the formula given in Section 2, the genus of this regular map is 8n(1/4 - 1/2n - 1/8) + 2 = n - 2 ifn is divisible by 3, and 24n(1/4 - 1/6n - 1/8) + 2 = 3n - 2 otherwise. In either case, we obtain a family of non-orientable regular maps of genera 3k - 2, for k = 1, 2, 3,..., as given also in [6]. This accounts for one-third of all positive integers. EXAMPLE 3.2. Let H be the subgroup of $6 generated by the three permutations u = (1,4)(2, 3)(5,6), v = (1,2,3, 4,5, 6) and t = (2, 6)(3, 5). Note that (u, v) is dihedral of order 12, and that t = uv 3. The subgroup generated by uv = ( 1, 5)(2, 4) and v 2 = (1, 3, 5)(2, 4, 6) is dihedral of order 6, and contains t, so the required conditions are fulfilled. In this case if w has order n, then ab has order 2n if n is odd, but n if n is even. Also since u 2 = v 6 - (uv) 2 -- 1 are defining relations for the dihedral group H, it follows that G = (a, b, c) has order 12 times the order of w 2, that is: IGI = 12n if n is odd, while IGI = 6n if n is even. Further, since uvt = v 2 has order 3, we find that order of abe = wuvt is equal to lcm(n, 3). In particular, ifn is odd then (abe) 3~ = 1 is a relation of odd length in the generators a, b, e of G, and hence the rotation subgroup (ab, be) has index 1 in G, and the corresponding map is non-orientable. By the given formula, the genus of this regular map is 12n(1/4 - 1/4n - 1/12) + 2 = 2n - 1. (On the other hand, if n is even, the defining relations for H show the rotation subgroup has index 2 in G, so the corresponding map is orientable in that case.) Letting n = 2k - 1, we thus obtain a family of non-orientable regular maps of genera 4k - 3, for k = 1, 2, 3, .... This accounts for 25 per cent of all positive integers, and when taken together with the family obtained in Example 3.1, accounts for exactly half: all 9 -= 1,4, 5, 7, 9 or 10 mod 12. EXAMPLE 3.3. Let H be the subgroup of $7 u = (1,2)(4,5)(6, 7), v = (2,3, 4)(6, 7) and isomorphic to A5 в C2, with uv = (1, 3, 4, 5, subgroup As, and v 3 = (6, 7) generating the generated by the three permutations t = (1,5)(2, 4). In this case H is 2) and v 2 = (2, 4, 3) generating the centre of order 2. The element t is


214

MARSTON CONDER AND BRENT EVERITT

not only contained in the former subgroup, but is also expressible as a product of conjugates of v 2. When we form the semi-direct product NH, the element ab has order n if n is divisible by 5, and 5n otherwise. On the other hand, as (abcbcb)2= (wuv3)2= w 2 we find G = (a, b, c) = NH, and therefore the group G has order 120n for every n. The corresponding map is non-orientable for all n (as in Example 3.1), since the element c is expressible as a product of conjugates of (cb) 2. The genus is 20n - 58 if n is divisible by 5, and 20n - 10 otherwise, and thus we have a family of nonorientable regular maps of genus 9 for all 9 = 10, 30, 42, 50 or 70 mod 100. Similar arguments are required for other examples. In most cases it is easy to determine exactly when the rotation subgroup (ab, be) has index 1 (by considering either conjugates of v or v 2, or the order of the product abe, for example). The difficulty lies in the calculation of the order of G, which largely depends on relations satisfied by the generators of the original group H. For permutation groups, however, this may be achieved by inspection or with the help of the 'relations' command in the CAYLEY system [2]. In Table 1 we list a number of examples which may be used as the 'top' group H in our-semi-direct product construction. Each item in the table yields an infinite family of non-orientable regular maps, all of which have the map corresponding to H (obtainable in the case n = 1) as a quotient. We provide generating permutations for H, state whether the construction works for all n or just for n odd, and describe the parameters of the regular map(s) which result, along with their genera. Many of these examples were found by searching for suitable permutation representations of the groups [p,q] = ( a, b, cla2 = b2 = c 2 = ( ab )P = ( bc )q = (ca) z = 1) for small p and q, using the 'low index subgroups' algorithm (available in the CAYLEY system [2]). Of course many other examples may be found, however their contribution to the genus spectrum will become less significant as their orders (and the parameters p and q) increase. 4. Results and Discussion The families of non-orientable regular maps presented in Section 3 account for over 77 per cent of all genera. To partly see how this comes about, note that the first two examples listed in Table I cover 6 of the 12 residue classes modulo 12, the first three cover 26 of the 48 residue classes modulo 48, and so on. In fact our families account for 29 547 540 of all residue classes modulo 38 102400 (=27355272), a little over 77.5 per cent of all positive integers. There are, of course, many sporadic examples with odd parameters, for example: G 3'7'9 =:- PSL(2, 8), of order 504, yields a regular map of non-orientable genus 8, while G 3'7'13 ~ PSL(2, 13), of order 1092, gives one of non-orientable genus 15 whose Petrie dual is also non-orientable and of genus 51 (see Table 8 in [4]), and finally G 5,5,5 '~ PSL(2, 11) of order 660 yields a regular map of non-orientable genus 35.


TABLE I. Generating permutations for H u = (l, 2) v = (1, 2, 3,4) t = (1, 2)(3, 4) all n type {3k, 4} u = (1,4)(2, 3)(5, 6) v =(1, 2, 3,4,5, 6) t = (2, 6)(3, 5) n odd type {2n, 6}
u = (1, 2)(5, 6)

Order of// 24

Genera g g =-- 1 mod3

12

g -- 1 mod4

48

g = 4mod 16

v = (2, 3, 4)(5, 6) t = (3, 4) n odd type {4n, 6} u = (1, 2)(3, 5)(6, 7)(8, 10) v = (2, 3, 7, 8)(4, 5, 9, 10)
t = (3, 8)(5,

160

g = 6 mod 20

10)

all n type {5k, 4} u = (1, 2)(4, 8)(5, 7) v = (1, 2, 3,4, 5, 6)(7, 8, 9) t = (1, 2)(3, 6)(4, 5) (7, 8) n odd type {6k, 6} u = (3, 5)(4, 7)(6, 10)(8, 11)(9, 13)(12, 14) v = (1, 2, 4, 8, 10, 14, 16, 15, 13, 11, 6, 3)(5, 7, 12, 9) t = (1, 2)(3, 4)(5, 7)(6, 8)(9, 12)(10, 11)(13, 14)(15, 16) n odd type {8n, 12} u = (1, 2)(5, 9)(6, 7)(8, 10)(11, 12) v = (1, 2, 4, 6, 10, 12,9,7, 11,8,5,3) t = (1, 2)(3, 4)(5, 6) (7, 9)(8, 10)(11, 12) n odd type {6k, 12} u = (2, 5)(4, 9)(6, 14)(7, 12)(8, 15)(10,19)(11, 21) (13, 24)(16, 25)(17, 28)(20, 23)(22, 30)(26, 29)(31, 32) v = (1, 2, 6, 15, 27, 20, 10, 4)(3, 8, 17, 21, 18, 9, 16, 7) (5, 11, 22, 30, 23, 12, 24, 13)(14, 25, 31, 29, 19, 28, 32, 26) t = (1, 3)(2, 7)(4, 8)(5, 12)(6, 16)(9, 15)(10, 17)(11, 23)(13, 24) (14, 25)(18, 27)(19, 28)(20, 21)(22, 30)(26, 31)(29, 32) all n type {5k, 8} 108 g = 11 mod36

96

g _~ 16mod40

144

g =- 20 mod 60

320

g = 30 mod 60


216
TABLE I. - continued Generating permutations for// u = (2, 5)(3, 4)(8, 11)(9, 10) v = (1, 2, 3)(4, 5, 7, 9, 8, 6)(10, 12, 11) t = (2, 3)(4, 5)(6, 7)(8, 9)(10, 11) n odd type {8n, 6} u = (2, 3)(4, 5)(6, 7) v = (1, 2, 3, 4, 5)(6, 7) t = (2, 5)(3, 4) all n type {3k, 10} u = (3, 4)(5, 6) v = (1, 2,4,6, 8, 7,5, 3) t = (1, 2)(3, 4)(5, 6)(7, 8) all n type {6k, 8} u = (1, 3)(2, 7)(4, 5)(6, 9)(8, 10) v = (1, 2)(3, 5)(4, 6, 8)(7, 10, 9) t = (1, 3)(2, 5)(4, 7)(6, 9)(8, 10) n odd type {4n, 6} u = (4, 5)(6, 7) v = (1, 2, 4,6, 8, 10,9,7,5,3) t = (2, 3)(4, 5)(6, 7)(8, 9) all n type {4k, 10} u = (1, 2)(4, 5)(6, 7) v = (2, 3, 4)(6, 7) t = (1, 5)(2, 4) all n type {5k, 6} u = (1, 2)(3, 6)(4, 7)(5, 8)(9, 11)(10, 12)(13, 14) v = (1, 3)(2, 4, 6, 5)(7, 9)(8, 10)(11, 13, 12, 14) = (4, 5)(7, 8)(9, 10)(11, 12) all n type {7k, 4} u = (2, 4)(3, 5)(6, 7) v = (1, 2, 3, 4, 5)(6, 7) t = (2, 5)(3, 4) all n type {5k, 10}

MARSTON CONDER AND BRENT BVERITT

Order of// 192

Genera g g - 22mod 64

120

g - 6, 14, 30rood72

384

g -- 42mod72

240

g - 12mod80

240

g - 20, 38 mod96

120

g - 10, 30, 42, 50, 70 mod 100

896

g - 50mod 112

120

g _----14, 38, 62, 86rood 120


TABLE I. - continued Generating permutations for H = (1, 2)(3, 4)(7, 8)(9, 10) v =(1,2,4,6,8, 10,9,7,5,3) t = (1, 2)(3, 4)(5, 6)(7, 8)(9, 10) n odd type {4n, 10} u = (1, 2)(3, 7)(4, 8)(5, 9)(6, 10)(11, 13)(12, 14) (15, 16)(17, 18) v = (1, 3, 6, 2, 5, 4)(7, 11, 15, 18, 14, 10) (8, 9, 13, 17, 16, 12) t = (3, 4)(5, 6)(7, 8)(9, 10)(11, 12)(13, 14)(15, 16) (17, 18) n odd Order of H 320 Genera g 9 ----26rood 128

432

g -- 56rood 144

type {12k, 6}
u = (1, 2)(3, 5)(6, 7) v = (2, 3, 4, 5)(6, 7) t = (3, 5) n odd type {6k, 4} n = (3, 4)(5, 7)(6, 8) v = (1, 2, 4, 6,8, 7,5, 3) t = (1, 2)(3, 4)(5, 6)(7, 8) all n 240 g ~ 12,32,132modlS0

336

g - 9, 23, 72 rood 189

type (3k, 8}
u = (3, 5)(4, 7)(6, 10)(8, 13)(9, 15)(12, 16) v = (1,2,4, 8, 14, 15, 13, 10, 16, 11,6,3) (5, 7, 12, 9) t = (1, 2)(3, 4)(5, 7)(6, 8)(9, 12)(10, 13) (11, 14)(15, 16) n odd type {12k, 12} u = (3, 5)(4, 6)(7, 10)(8, 12)(9, 11) v = (1, 2, 4, 3)(5, 7, 11,8)(6,9, 12, 10) t = (I, 2)(3, 4)(5, 6)(7, 10)(8, 9Xll, 12) all n type {9k, 4} = (3, 5)(4, 7)(6, 8) v = (I, 2, 4, 8,7, 5,6, 3) t = (1, 2)(3, 4)(5, 7)(6, 8) all n type {4k, 8} u = (2, 5)(4, 8)(6, 10)(7, 11)(9, 13)(12, 15) v = (1, 2, 6, 4)(3, 7, 9, 5)(8, 10, 14, 12) (11, 15, 16, 13) t = (1, 3)(2, 5)(4, 7)(6, 9)(8, 11)(10, 13) (12, 15)(14, 16) all n type {6k, 4} 576 g - 98 mod 240

648

g--47,128,137mod243

336

g = 23, 44, 86, 149rood252

672

g =_ 30, 86, 114 mod 252


218 .TABLE I. - continued Generating permutations for H u = (1, 3)(4, 11)(6, 13)(7, 8)(9, 10)(14, 16) v = (1, 2, 6, 4)(3, 7, 9, 5)(8, 10, 14, 12) (11, 15, 16, 13) = (1, 3)(2, 5)(4, 7)(6, 9)(8, 11)(10, 13) (12, 15)(14, 16) all n type {8k, 4} u = (3, 5)(4, 7)(6, 8) v =(1, 2,4,8,6, 3) t = (1, 2)(3, 4)(5, 7)(6, 8) all n type {7k, 6} u = (1, 2)(5, 8)(6, 7) v = (1, 2,4,6, 8, 7,5, 3) t = (1, 2)(3, 4)(5, 6)(7, 8) all n type {7k, 8} u = (1, 2)(3, 4)(5, 8)(6, 10)(7, 9) v=(1, 10,9,3,7,2,5,6,8,4) t = (3, 6)(4, 10)(5, 7)(8, 9) all n type {5k, 10}

MARSTONCONDERAND BRENTEVERITT

Order of// 672

Genera g g -- 44, 86, 170, 212mod336

336

g ~ 34,90,146,202,226,258, 314 mod392

336

g --- 41,104, 167,230, 275,293, 356 mod441

720

g - 74, 218,362,506 mod 720

Every positive integer g ___ 100 other than 2, 3, 18, 24, 27, 39, 48, 54, 59, 60, 63, 71, 75, 87, 95 and 99 is known to be the genus of some non-orientable regular map. Of the exceptions, non-orientable surfaces of genus 2 or 3 are definitely known not to admit regular maps (see [4]), and we believe 18, 24 and 27 have also been eliminated by Steve Wilson (private communication). What of the remaining genera? As our method requires (at least) one of the parameters to be even, its scope is limited. As well as this, examples larger than those we have provided will produce relatively fewer new possibilities, and so it would seem unlikely that our method will yield much more than it already has but who knows? The true picture is still far from clear.

Acknowledgements
The first author is grateful to Martin Skoviera and Roman Nedela for bringing this problem to his attention, to Steve Wilson for helpful comments, and to the


REGULAR MAPS ON NON-ORIENTABLE SURFACES

219

Auckland University Research Committee for research support. The second author acknowledges the assistance of an Auckland University Doctoral Scholarship.
References
1. Biggs, N. L. and White, A. T.: Permutation Groups and Combinatorial Structures, L.M.S. Lecture Note Series, vol. 33, Cambridge University Press, 1979. 2. Cannon, J. J.: An introduction to the group theory language CAYLEY, in M. Atkinson (ed.), Computational Group Theory, Academic Press, San Diego, London, 1984, pp. 145-183. 3. Coxeter, H. S. M.: The abstract groups G .... P, Trans. Amer. Math. Soc. 45 (1939), 73-150. 4. Coxeter, H. S. M. and Moser, W. O. J.: Generators and Relations for Discrete Groups, 4th edn, Springer-Verlag, Berlin, 1980. 5. Wilson, S. E.: Operators over regular maps, PacificJ. Math. 81 (1979), 559-568. 6. Wilson, S. E.: Cantankerous maps and rotary embeddings of K,,, J. Combin. Theory Series B 47 (1989), 262-273.