ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 10 (2016) 237-254 Combinatorial categories and permutation groups Gareth A. Jones * School of Mathematics, University of Southampton, Southampton SO171BJ, U.K. Received 24 September 2013, accepted 22 July 2015, published online 20 October 2015 The regular objects in various categories, such as maps, hypermaps or covering spaces, can be identified with the normal subgroups N of a given group r, with automorphism group isomorphic to r/N. It is shown how to enumerate such objects with a given finite automorphism group G, how to represent them all as quotients of a single regular object U(G), and how the outer automorphism group of r acts on them. Examples constructed include kaleidoscopic maps with trinity symmetry. Keywords: Regular map, regular hypermap, covering space, permutation group, category. Math. Subj. Class.: 20B25, 05A15, 05C10, 05E18, 20J99, 57M10 1 Introduction In certain categories C, the objects O can be identified with the permutation representations of a particular group r = rC on sets $ = , and the morphisms O ^ O' correspond to the functions ^ $o> commuting with the actions of r. In the case of maps on surfaces one takes r to be the free product V4 * C2 acting on flags, or * C2 acting on directed edges of oriented maps. The corresponding groups for hypermaps are C2 * C2 * C2 and the free group F2 = * of rank 2. For abstract polytopes of a given type one can use the corresponding string Coxeter group, again acting on flags, though here one has to restrict attention to quotient groups satisfying the intersection property. In the case of coverings of a path-connected space X one uses the fundamental group n^X, acting on sheets or more precisely on the fibre over a base-point. *The author thanks the organisers of GEMS 2013 for inviting and supporting him to give a talk summarising this paper. It is based upon work supported by the project: Mobility — enhancing research, science and education at the Matej Bel University, ITMS code: 26110230082, under the Operational Program Education cofinanced by the European Social Fund. E-mail address: G.A.Jones@maths.soton.ac.uk (Gareth A. Jones) Abstract ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 237 Ars Math. Contemp. 10 (2016) 393-410 In such a case we will call C a permutational category, with parent group r. Each object O in such a category C is a disjoint union of connected subobjects, corresponding to the orbits of r on $; one usually restricts attention to the connected objects, as we shall here, so that $ can be identified with the set of cosets in r of a point-stabiliser M = T^, where ^ € $. The permutation group induced by G on $ is the monodromy group G = Mon O = MonCO of O, a subgroup of the symmetric group Sym $ on $. The automorphism group A = Aut O = AutCO of O, regarded as an object in C, is the centraliser of G in Sym $; since G is transitive on $, A acts semiregularly on $, and A = Nr(M )/M = Ng(G0 )/G0. The most symmetric objects in C are the regular objects, those for which A acts transitively (and hence regularly) on $. This is equivalent to M being a normal subgroup of r, in which case A = r/M = G. Indeed, in this case A and G can be identified with the left and right regular representation of the same group. In principle, understanding regular objects is sufficient for an understanding of all objects in C, since each object O € C is the quotient of some regular object O € C, corresponding to the core N of M in r, by a group M/N of automorphisms of O; moreover, O is finite if and only if O is finite, since N has finite index in r if and only if M has finite index. We shall therefore concentrate, for the remainder of this paper, on the regular objects in various categories C. In particular, we will study the set R(G) = RC(G) of regular objects O € C with Aut O isomorphic to a given group G. If r is finitely generated and G is finite then r(G) := |R(G)| is finite. We will consider how to calculate r(G) in this case, how to represent the objects in R(G) as quotients of a single regular object U(G) in C, and how the outer automorphism group Out r of r acts on R(G). Examples will be given, in which the objects are maps, hypermaps or surface coverings, some of them relevant to recent work by Archdeacon, Conder and Siran on kaleidoscopic maps with trinity symmetry [1]. 2 Examples of permutational categories Let us call a category C a permutational category if it is equivalent to the category of permutation representations of some group r, called the parent group of C. This means that there are functors from each category to the other, so that their composition, in either order, is naturally equivalent to the identity. There are some well-known examples in the literature, though the equivalences are rarely expressed in terms of categories. We will summarise them briefly here; for further details, see, for example, [33] for maps, and [26] for hypermaps. The category M of maps on surfaces, with branched coverings of maps as its mor-phisms, is a permutational category, with parent group r = = (Rq| R? = (R0R2)2 = 1). (2.1) Here each R acts on the set $ of vertex-edge-face flags of a map O € M by changing, in the only way possible, the ¿-dimensional component of each flag while preserving its j-dimensional component for each j = ¿. (A boundary flag is fixed by R if no such change is possible.) This group, which is a free product (Rq,R?)*(Ri) = V4 * C? G. A. Jones: Combinatorial categories and permutation groups 239 of a Klein four-group and a cyclic group of order 2, can be regarded as the extended triangle group A[to, 2, to] of type (to, 2, to), generated by reflections in the sides of a hyperbolic triangle with angles 0, n/2,0. This gives a functor from maps to permutation representations of r. Conversely, given a permutation representation of r on a set $, one can take a set of triangles in bijective correspondence with $, each with vertices labelled 0,1,2, and use the cycles of Rj on $ to join pairs of triangles across edges jk (j, k = i); the result is the barycentric subdivision of a map O g M, with the vertices of O labelled 0 and its edges formed by edges of triangles labelled 01, so that midpoints of edges and faces of O are labelled 1 and 2. Branched coverings between maps O correspond to T-equivariant functions between sets $, so we obtain functors O ^ $ and $ ^ O which give the required equivalence of categories. Other triangle groups act as parent groups for related categories. For the category Mk of maps with all vertex-valencies dividing k we add the relation (RiR2)fc = 1 to the presentation (2.1), giving the parent group rOTfc = (Rc,Ri,R2 | R? = (R0R2)2 = (RiR?)k = 1) = A[k,2,to]. (2.2) Similarly, the isomorphic group A[to, 2, k] is the parent group for the dual maps, with all face-valencies dividing k. For the category H of hypermaps, where hyperedges may be incident with any number of hypervertices and hyperfaces, we delete the relation (R0R2 )2 = 1 from (2.1), giving the parent group rH = (R0, R1, R? | R? = 1) = A[to, to, to] = C? * C? * C? (2.3) again permuting flags. Similarly, the extended triangle group A[/, m, n] = (Ro, Ri, R? | R? = (RiR?)1 = (RoR?)m = (RoRi)n = 1) is the parent group for hypermaps of type dividing (/, m, n), that is, of type (/', m', n') where /', m' and n' divide /, m and n. For the corresponding categories M+, M+ and H+ of oriented maps and hypermaps we take the orientation-preserving subgroups of index 2 in these groups, generated by the elements X = RiR0, Y = R0R? and Z = R?Ri satisfying XYZ = 1. These are the triangle groups rM+ = (X, Y, Z | Y? = XYZ =1) = A(to, 2, to) = * C?, (2.4) rM+ = (X, Y, Z | Xk = Y? = XYZ =1) = A(k, 2, to) = Ck * C? (2.5) and rH+ = (X, Y, Z | XYZ =1) = A(to, to, to) = * = F?. (2.6) Similarly, the triangle group A(/, m, n) = (X, Y, Z | X1 = Ym = Zn = XYZ = 1) is the parent group for oriented hypermaps of type dividing (/, m, n). In the case of oriented hypermaps, the Walsh map [51] represents a hypermap as a bipartite map, with black and white vertices representing hypervertices and hyperedges, and edges representing their incidence; then X and Y permute the set $ of edges by following 47 Ars Math. Contemp. 10 (2016) 393-410 the local orientation around their incident black and white vertices. For oriented maps, X rotates directed edges around their target vertices, while Y reverses them; equivalently, one can convert a map into the Walsh map of a hypermap by adding a white vertex at the centre of each edge, so that new edges correspond to directed edges of the original map. If X is a path connected, locally path connected, and semilocally simply connected topological space [43, Ch. 13]), the unbranched coverings fi : Y ^ X of X form a permutational category C with the fundamental group r = niX as parent group, using unique path-lifting to permute the fibre $ = fi-1 (x0) C Y of fi over a chosen basepoint x0 € X. The regular coverings fi correspond to the normal subgroups N of r, with covering group Aut fi = r/N. If X is also a compact Hausdorff space (for instance, a compact manifold or orbifold), then r is finitely generated [43, p. 500]. The categories of maps and hypermaps described above can be regarded as obtained in the above way from suitable orbifolds X, such as a triangle with angles n/l, n/m, n/n for hypermaps of type dividing (l, m, n), or a sphere with three cone-points of orders l, m, n in the oriented case. Similarly, Grothendieck's dessins d'enfants [21, 22] are the finite coverings of a sphere minus three points, so their parent group is its fundamental group r = F2, with generators X, Y and Z inducing the monodromy permutations at the three punctures. For the rest of this paper, C will denote a permutations category with a finitely generated parent group r. 3 Counting regular objects For each group G, there is a natural bijection between the set R(G) = RC(G) of (isomorphism classes of) regular objects O € C with Aut O = G and the set N(G) = Nr(G) of normal subgroups N of r with r/N = G. These normal subgroups are the kernels of the epimorphisms r ^ G. Two such epimorphisms have the same kernel if and only if they differ by an automorphism of G, so there is a bijection between N(G) and the set of orbits of Aut G, acting by composition on the set Epi(r, G) of epimorphisms r ^ G. This action of Aut G is semiregular, since only the identity automorphism of G fixes an epimorphism. If G is finite then so is Epi(r, G), since each epimorphism r ^ G is uniquely determined by the images in G of a finite set of generators of r. In this case the sets R(G) and N(G) have the same finite cardinality r(G) = rc(G) = |R(G)| = n(G) = nr(G) = |N(G)| = ^q^ . (3.1) In [24], Hall developed a method for counting epimorphisms onto G by first counting homomorphisms (generally an easier task) to subgroups of G, and then using Mobius inversion in the lattice A(G) of subgroups of G. Let a and ^ be functions from isomorphism classes of finite groups to C such that a(G) = £ ¿(H) (3.2) H H with 6H,a = 1 if H = G and 0 otherwise. (One can view this as a group-theoretic analogue of the inclusion-exclusion principle, which applies to the lattice of all subsets of G; in that situation, by replacing the condition K > H in (3.4) with K D H one assigns the value (-1)|a\H| to ya(H) for each subset H of G.) Each homomorphism r ^ G is an epimorphism onto a unique subgroup H < G, so one can take (n), while the automorphism groups of the finite simple groups are all known and can be found in sources such as [5, 52]. Finding the other two ingredients is generally more troublesome, and this has been achieved only in special cases. 4 Evaluating the Mobius function Evaluating the Mobius function requires detailed knowledge of the subgroup lattice of G. It has been achieved for several infinite classes of groups G, and of course for specific groups which are not too large one can use systems such as GAP or MAGMA. In this context, the database of subgroup lattices described by Connor and Leemans in [4], and available at [3], is a valuable resource. 49 Ars Math. Contemp. 10 (2016) 393-410 Example 4.1 A finite cyclic group G = Cn of order n has a unique subgroup H = Cm for each m dividing n, and no other subgroups. Hall [24] showed that pG(H) = p(n/m), where p is the Mobius function of elementary number theory, given by p(n) = ( — 1)k if n is a product of k distinct primes, and p(n) = 0 otherwise. Indeed, here p can be regarded as the Mobius function on the lattice of subgroups of finite index in the infinite cyclic group Z. Example 4.2 Similarly, it is an easy exercise to compute the Mobius function for a finite dihedral group; see [28]. Example 4.3 An elementary abelian group G of order pd can be regarded as a vector space of dimension d over the field Fp, and its subgroups H as the linear subspaces. The number of these of each codimension k = 0,1,..., d is equal to the Gaussian binomial coefficient d N (pd — 1)(pd-1 — 1) ... (pd-fc+! — 1) k) p (pk — 1)(pk-1 — 1)... (p — 1) ' and Hall [24] showed that they satisfy Mg(H ) = (—1)y(k-1)/2. Hall showed that in any finite group G, if pG(H) = 0 then H must be the intersection of a set of maximal subgroups of G, so in particular H must contain the Frattini subgroup $(G) of G, the intersection of all its maximal subgroups. Example 4.4 If G is a d-generator finitep-group then $(G) is the subgroup G'Gp generated by the commutators and p-th powers in G, and G/$(G) is an elementary abelian p-group of order pd. The subgroups H < G with pG(H) = 0 all contain $(G), and correspond to the subgroups of G/$(G), with pG(H) given by the preceding example. If G = G1 x G2 where G1 and G2 are finite groups of coprime orders, each subgroup H < G has the unique form H = H1 x H2 where H < Gj. In this case Hall showed that PG(H) = PGi (H1)PG2 (H2). Example 4.5 Each nilpotent finite group G is a direct product of its Sylow subgroups, which are p-groups for the different primes p dividing |G|, so the preceding examples show how to compute pG. Example 4.6 Dickson described the subgroups of the groups L2(q) = PSL2(q) in [7, Ch. XII]. Using this, Hall [24] calculated the Mobius function pG for the simple groups G = L2 (p) for primes p > 5. Equation (3.3) takes the form ¿(G) = a(G) — (p + 1)a(GTO) — a(Dp+i) — p(p + 1) dp-i + p(p +1)CT(Cp_i) + |G|S, where is the subgroup of index p +1 fixing to, and S depends on the congruence classes of p mod (5) and mod (8), which determine the existence of proper subgroups H = or S4. For example, if p = 5, or if p = ±2 mod (5) andp = ±3 mod (8), so that there are no such subgroups, then s = —12 a(A4) + 4 *(V4) + 1 ^(Cs) + 1 a(C2) — <7(1); G. A. Jones: Combinatorial categories and permutation groups 239 there are similar formulae in the other cases. In [10] Downs extended Hall's calculation of ^a to L2(q) and PGL2(q) for all prime powers q; see [11] for a proof for L2(2e) and a statement of results for L2 (q) where q is odd, and [13] for some combinatorial applications by Downs and the author. Example 4.7 The Suzuki groups G = Sz(q) are a family of non-abelian finite simple groups, with q = 2e for some odd e > 1; see [5, 50, 52] for their properties, which are similar to those of the groups L2(2e). Downs calculated ^a for these groups in [12]; see [14] for a statement of the results and some applications. 5 Counting homomorphisms In order to apply equation (3.7) to a group G, one needs to evaluate |Hom(r, H) | for those subgroups H < G with ^a(H) = 0. If r has a presentation with generators X; and defining relations Rj, this is equivalent to counting the solutions (x;) in H of the equations Rj(xj) = 1. Example 5.1 If r is a free product Cmi *• • *Cmfc of cyclic groups of orders m; G NU{to}, then k |Hom(r, H )| = HE |H |m j= 1 m| mi where |H |m denotes the number of elements of H of order m, and we regard all orders m as dividing to, so that J2m|TO |H|m = |H|. For instance, if r is a free group Fk of rank k then |Hom(r, H)| = |H|k. Similarly, the torsion theorem for free products [36, Theorem IV.1.6] implies that a homomorphism r ^ H is smooth if and only if it embeds each finite factor Cmi, so the number of such homomorphisms can be found by multiplying k factors equal to |H \mi or |H | as m; is finite or infinite. For certain groups r, the character table of H gives |Hom(r, H) |. Example 5.2 If r is a polygonal group A(mi,...,mk) = {Xi,...,Xk | X^"1 = ... = Xfcmfc = X ...Xk = 1) of type (m1,..., mk) for some integers m;, then |Hom(r, H)| can be found by summing the following formula (5.1) of Frobenius [18] over all choices of k-tuples of conjugacy classes of elements of orders dividing m;. Theorem 5.1. Let (i = 1,..., k) be conjugacy classes in a finite group H. Then the number of solutions of the equation x1... xk = 1 in H, with x; G for i = 1,..., k, is \Ci\... \Ck\ y^ X(xi)... X(xk) (51) |H\ ^ x(1)k-2 ) where x; G C; and x ranges over the irreducible complex characters of H. Similarly, the number of smooth homomorphisms r ^ H can be found by restricting the summation to classes of elements of order equal to m;. The case k = 3 of this theorem, where r is a triangle group, has often been used in connection with oriented maps and hypermaps: see [27] and [32], for instance. 51 Ars Math. Contemp. 10 (2016) 393-410 Example 5.3 If r is an orientable surface group ng, that is, the fundamental group g ns = nlSg = (Ai, Bi (i = 1,..., g) | fl[Ai, B] = 1) i= 1 of a compact orientable surface Sg of genus g > 1, one can use the following theorem of Frobenius [18] andMednykh [42], which counts solutions of the equation f]g=1[ai, bi] = 1: i=1 Theorem 5.2. If H is any finite group then |Hom(ng, H)| = |H|2g-1 £x(1)2-2g, (5.2) x where x ranges over the irreducible complex characters of H. Example 5.4 If r is a non-orientable surface group g n- = (Ai (i = 1,..., g) ^ A2 = 1) A2 ¿=i of genus g > 1, one can use the following result of Frobenius and Schur [19]: Theorem 5.3. If H is a finite group then |Hom(n- H)| = |H|g-1 Y 4x(1)2-s, (5.3) x where x ranges over the irreducible complex characters of H. Here cx is the Frobenius-Schur indicator |H|-1 J2heH x(h2) of x, equal to 1, -1 or 0 as x is the character of a real representation, the real character of a non-real representation, or a non-real character. See [28] for applications of these two theorems, and [48, Ch. 7] for several generalisations of them. 6 Enumerations Using Theorem 3.1 one can now enumerate, for a given finite group G, the regular objects in C with automorphism group G, and also the objects in C with monodromy group G. Example 6.1 It follows from a result of Hall [24] that if G = L2 (p) for some prime p > 5 and C = H+, so that r = F2, then r(G) = 1(p +1)(p2 - 2p - 1) - e, where e = 49, 40, 11 or 2 as p = ±1 mod (5) and ±1 mod (8), or ±1 mod (5) and ±3 mod (8), or ±2 mod (5) and ±1 mod (8), or ±2 mod (5) and ±3 mod (8). We also take e = 2 when p = 5, so that r(G) = 19 in this case; the 19 regular oriented hypermaps associated with the icosahedral group G = L2 (5) = A5 have been described by Breda and the author in [2]. Since this group G has eight conjugacy classes of proper subgroups, all with trivial core since G is simple, it follows from equation (3.8) that there are 19 x 8 = 152 oriented G. A. Jones: Combinatorial categories and permutation groups 239 hypermaps with monodromy group G, namely the quotients O/H where O G R(G) and H < G. Example 6.2 In [10], Downs considered the categories H, H+, M, M+, M3 and M+, and gave formulae for r(G) where G = L2 (q) or PGL2 (q) for any prime power q. The results for G = L2(2e) are given in [13]. Typical results for odd q are: rm(L2(pe)) = £ M ( eW(Pf - a) for all p > 2 and odd e > 1, where a = 2 or 4 as p = 1 or -1 mod (4), and rOT3(PGL2(pe)) = 4e EM f (Pf - 1) for p > 3 and e > 1, where the sum is over all factors f of e with e/f odd. Example 6.3 Using Downs's calculation of the Mobius function for G = Sz(2e) in [12], he and the author have enumerated various combinatorial objects with automorphism group G in [14]. Typical results are that r«+ (G) = 1 E M (7) 2f (24f - 23f - 9) and rM(G) = 1 E^7) (2f - 1)(2f - 2). 7 f|e The second formula, which also gives the number of reflexible maps in (G), has been obtained by more direct means by Hubard and Leemans in [25]. Example 6.4 If G is infinite then R(G) could be finite or infinite. For instance, if C = H+, so that r = F2, then r(Z2) = 1 whereas r(Z) = H0. 7 Universal covers For any group G, and any C, let K(G) = Kc(G)= H N. (7.1) N eN (G) This is a normal subgroup of r, so it corresponds to a regular object U(G) = WC(G)= V O (7.2) OeR(G) which we will call the universal cover for G, the smallest object in C covering each O G R(G). This has automorphism group G := AutU(G) =r/K(G). (7.3) 53 Ars Math. Contemp. 10 (2016) 393-410 If r has generators X (i G I) then one can realise G as the subgroup of the cartesian power GR(G) of G generated by the elements (xji, xj2,...) for i G I, where is the image of X in G = Aut for some numbering O1,02,... of the objects Ok G R(G). In particular, G has the same number of generators as r, and it satisfies all the identical relations satisfied by G: for instance, if G is nilpotent of class c, is solvable of derived length d, or has exponent e, then the same applies to G. Finally, if G is finite, as we will assume from now on, then so are U(G) and G, with |G| dividing |G|r where r = r(G). Example 7.1 Let C = H+, so that r = F2. If G = Cn then K(G) = Frn, so g = r/r'rn = cn x cn. Represented as a bipartite map, the hypermap U (G) is a regular embedding of the complete bipartite graph Kn,n in a surface of genus (n - 1)(n - 2)/2. In fact, we obtain the same universal cover U(G) and group G whenever G is a 2-generator abelian group of exponent n. This example shows that G can be a rather small subgroup of Gr, since G = G2 whereas r > n. However, if G is a non-abelian finite simple group, then the following result shows that G = Gr for any category C; see [29] for a proof. Lemma 7.1. Let N1,..., Nr be distinct normal subgroups of a group r, with each Gj := r/N non-abelian and simple. If K = N1 n • • • n Nr then r/K = G1 x ••• x Gr. Taking {N1,..., Nr } = Nr(G), so Gj = G for i = 1,..., r, gives the result. Example 7.2 Let C = H+ again, and let G = L2(5) = A5. By Example 6.1 we have r(G) = 19, so G = G19, of order 6019 = 609359740010496 x 1017 « 6.1 x 1031. Guralnick and Kantor [23] have shown that if G is a non-abelian finite simple group then each non-identity element of G is a member of a generating pair. If such a group G has exponent e then it follows that (G) has type (e, e, e), so by the Riemann-Hurwitz formula it has genus g = 1 + fi3 iGir • In Example 7.2, for instance, G has exponent 30, so (G) has genus 1 + — x 6019 = 274218830047232000000000000000001 « 2.742 x 1031. 20 For any finite group G we have |Epi(F2, G)| < |G|2, so I G|2 |G|.|Z(G)| r«+ (G) < |Aut G| |Out G| where Out G is the outer automorphism group Aut G/Inn G of G. In particular, if G has trivial centre then r«+ 1, the automorphism group of Fn is generated by the elementary Nielsen transformations: permuting the free generators, inverting one of them, and multiplying one of them by another [40, Theorem 3.2]. When n = 2 one can identify Q = Out r with GL2 (Z) through its faithful induced action on the abelianisation rab = r/r Z2 of r [38, Ch. I, Prop. 4.5]. This group Q can be decomposed as a free product with amalgamation as follows (see [6, §7.2] for presentations of Q). If we take the images of X and Y as a basis for rab, then there is a subgroup E = S3 = D3 of Q, generated by the matrices E =(! 0) and (-1 -i of order 2 and 3; this group, which simply permutes the three vertex colours of an oriented hypermap, regarded as a tripartite map by stellating its Walsh map, was introduced by Machi in [39]. The central involution -I of Q reverses the orientation of each hypermap and, together with E, generates a subgroup Qi = E x (-I) = S3 x C2 = De of Q which preserves the genus of each hypermap and permutes the periods in its type. If a hypermap is represented as a bipartite map, then the matrices -1 0 ^ A ( 1 0 0 1) and [0 -1 reverse the cyclic order of edges around each black or white vertex, while preserving the order around those of the other colour; they are sometimes called Petrie operations, since they preserve the embedded bipartite graph but replace faces with Petrie polygons (closed zig-zag paths), so the genus may be changed. These two matrices, together with E, generate a subgroup Q2 = D4 such that Q0 := Q1 n Q2 = (E, -I) = V4 = D2 G. A. Jones: Combinatorial categories and permutation groups 239 and Q = Q1 *q0 Q2 = DQ *d2 D4. The torsion theorem for free products with amalgamation [36, Theorem IV.2.7] shows that the operations of finite order are the conjugates of the elements of Q1 U Q2, described by Pinto and the author in [30]. For any 2-generator group G, the orbits of Q on R(G) correspond to the T2-systems in G, that is, the orbits of Aut F2 x Aut G acting by composition on Epi(F2, G) and hence on generating pairs for G. It is known [15, 45] that this action is transitive if G is abelian, whereas Garion and Shalev [20] have shown that if G is a non-abelian finite simple group then the number of orbits tends to to as |G| ^ to. Example 8.1 It follows from work of Neumann and Neumann [45] that the 19 hypermaps in R(A5) form two orbits of lengths 9 and 10 under Q, which acts as S9 x S10 on them. Those hypermaps whose type is a permutation of (2,5,5), (3,3, 5) or (3, 5,5)- form the first orbit, while those of type a permutation of (2,3,5), (3, 5, 5)+ or (5, 5,5) form the other; here the superscript + or - indicates that the generators of order 5 are or are not conjugate in A5. This example illustrates a useful result of Nielsen [46], that when r = F2 the order of the commutator [x, y] is an invariant of the action of Q on R(G) for any group G: here the order is 3 or 5 for the hypermaps in the two orbits. 8.2 Operations on all hypermaps When C = H we have r = C2 *C2 *C2, containing F2 as a characteristic subgroup of index 2. As shown by James [26] there is again an action of GL2 (Z) on hypermaps, as described above, but now extended to all hypermaps. In this case -I, induced by conjugation by R1, is in the kernel of the action (since any orientation is now ignored), and there is a faithful action on H of the group Outr = gl2(z)/(-i) = pgl2(z) = s3 *c2 v4. 8.3 Operations on oriented maps When C = M+ we have r = * C2, with Q = Outr = V4. This group Q is generated by vertex-face duality, induced by the automorphism of r transposing X and Z, and orientation-reversal, induced by inverting X and fixing Y . These two involutions commute, modulo conjugation by Y . If we restrict to the category M+ of oriented maps of valency dividing k, then r = Ck *C2, with Q isomorphic to the multiplicative group Z*k of units mod (k) provided k > 2. The elements of Q are the operations Hj defined by Wilson in [53], raising the rotation of edges around each vertex to its jth power, and induced by automorphisms fixing Y and sending X to Xj for j e Z*k. These operations Hj, studied by Nedela and Skoviera in [44], preserve the embedded graph, but can change the surface. When k = 5, for instance, H2 transposes the icosahedron and the great dodecahedron. 8.4 Operations on all maps When C = M we have r = V4 * C2, with Q = Out r = S3 induced by the automorphism group of the free factor (R0, R2) = V4 permuting its three involutions R0, R2 and R0R2. 57 Ars Math. Contemp. 10 (2016) 393-410 As shown by Thornton and the author [33], this group Q is simply an algebraic reinterpretation of the group of operations on regular maps introduced by Wilson in [53] (see also [37]). It is generated by the classical duality of maps, which transposes vertices and faces by transposing R0 and R2, and the Petrie duality, which transposes faces and Petrie polygons by transposing R0 and R0R2; these two operations have a product of order 3 which acts as a triality operation, cyclically permuting the sets of vertices, faces and Petrie polygons of each map. As noted by Wilson, maps admitting trialities but not dualities seem to be rather rare: Poulton and the author have given some infinite families of examples in [31]. If we restrict to the category Mk of maps of valency dividing k, then r = A[k, 2, rc] = (Ro, Ri> *(Ro> (Ro, R2> = Dk *C2 D2, where the amalgamated subgroup C2 is generated by a reflection R0 in each factor. If k > 2 the automorphisms of Dk fixing R0 form a group isomorphic to Z*k, sending R0Ri to (R0Ri)j for any j e Z*k, while those of D2 fixing R0 simply permute R2 and R0R2. These extend to automorphisms of r which generate a subgroup Z*k x C2 of Aut r: the first factor induces Wilson's operations Hj, and the second factor induces Petrie duality. The structure theorems for free products with amalgamation [36, §7.2] show that this subgroup maps onto Out r. Since H-i is induced by conjugation by R0 we find that Q - (Zk/{±1}) x C2. When k = 3, with Q = C2, we obtain the outer automorphism of the extended modular group r = PGL2(Z) studied by Thornton and the author in [34]. 8.5 Operations on surface coverings If Sg is an orientable surface of genus g > 1, and r = niSg, then by the Baer-Dehn-Nielsen Theorem the group Q = Out r is isomorphic to the extended mapping class group Mod±(Sg) of Sg, that is, the group of isotopy classes of self-homeomorphisms of Sg (see [17, Ch. 8]). The mapping class group Mod(Sg) is the subgroup of index 2 corresponding to the orientation-preserving self-homeomorphisms; both groups are finitely presented, with ModSg generated by the Dehn twists [17, Ch. 3]. The induced action of Mod±(Sg) on coverings of Sg corresponds to the action of Q on permutation representations of r. Example 8.2 If g = 1 thenr - Z2 and Q = Mod±(Si) = GL2(Z), with Mod(Si) corresponding to SL2 (Z). This is generated by the Dehn twists corresponding to the elementary matrices j D and f11 9 Invariance under operations Although it is natural to regard the regular objects in C as its most symmetric objects, some of these may have additional 'external' symmetries, in the sense that they are invariant (up to isomorphism) under some or all of the operations in Q. Self-dual maps, such as the tetrahedron, are obvious examples. For any C and G the group K(G) defined in (7.1) is a characteristic subgroup of r, so the corresponding regular object U(G) is invariant under G. A. Jones: Combinatorial categories and permutation groups 239 Q. This shows that each object O g C, regular or not, is covered by an Q-invariant regular object U(G) g C, which is finite if and only if O is, and which has automorphism group G where G = Mon O. The smallest Q-invariant regular object covering O can be obtained by restricting the normal subgroups N in (7.1) to those in the appropriate orbit of Q on Nr (G). Richter, Siran and Wang [47] have shown that for infinitely many k there are regular k-valent maps which are invariant under the group of operations Qi := Qm = S3 (see also [33, Theorem 3]), while Archdeacon, Conder and Siran [1] have recently constructed infinite families of k-valent orientably regular maps invariant under both Qi and the group Q2 := Qm+ = Z*k. They call these 'kaleidoscopic maps with trinity symmetry'. In both cases, examples of such maps can be constructed as maps Um(G) for finite groups G: for instance, the map denoted by Mn in [1, Theorem 2.2] has this form where G is a dihedral group of order 4n, with k(G) = r"(r')n in r = rm ^ v4 * c2. The connection is as follows. For orientably regular maps, invariance under the operation H_1 g Q2 is equivalent to reflexibility, so one needs to find normal subgroups of r which are invariant under the actions of Q1 = Outr (i.e. which are characteristic subgroups of r) and (for kaleidoscopic maps) of Q2 = Z*k, where k is the valency of the corresponding map. For any quotient G of r, these two groups Qi act by permuting the subgroups in Nr(G), so they leave invariant their intersection K(G); the map U(G) corresponding to K(G) is therefore kaleidoscopic with trinity symmetry. Example 9.1 Let G = A5, so that the three maps Mi (i = 1, 2, 3) in R(G) are the antipodal quotients of the icosahedron, the dodecahedron and the great dodecahedron (see Example 7.4); these have types {3,5}5, {5,3}5 and {5,5}3 where the subscript denotes Petrie length, as in [6, §8.6]. Their join U(G) is a non-orientable regular map of type {15,15} 15 and genus 39602, with automorphism group G = A5. The groups Q1 and Q2 permute the three maps Mi (Q1 transitively, while Q2 = Z15 = C2 x C4 has orbits {M2} and {M1, M3}), so U(G) is kaleidoscopic with trinity symmetry. (This is the non-orientable example constructed by a different method in [1, §7].) Example 9.2 For an orientable example, we can take G = A5 x C2, so U(G) is the join of U(A5), described in the preceding example, and U(C2), a reflexible map of type {2,2}2 on the sphere corresponding to the derived group K(C2) = r' of r. This gives an orientable map of type {30,30}30 and genus 187201, which is kaleidoscopic with trinity symmetry and has automorphism group (A5 x C2)3. More generally, if G is a non-abelian finite simple group which is a quotient of r (the only ones which are not are ¿3(9), U(q), £4(2®), U4(2e), Ae, A7, Mn, M22, M23 and McL, according to [49, Theorem 4.16]), these constructions yield a pair of non-orientable and orientable kaleidoscopic maps which have trinity symmetry and have automorphism groups Gr and Gr x C2, where r = rm(G). Example 9.3 If G is the Suzuki group Sz(8), of order 2e.5.7.13 = 29120, then r = 14 by Example 6.3; the resulting maps have types {k, k}k and {2k, 2k}2k where k = 455, the 59 Ars Math. Contemp. 10 (2016) 393-410 least common multiple of the valencies 5, 7 and 13 of the vertices in the 14 maps in R(G) (see [14]). The orientable map has genus 2912014 x 23 453 13 1 +- x -= 1 + 29120 x 28992. 4 910 If only trinity symmetry is required, as in [47], then smaller examples of this type can generally be found, with r dividing 6, by replacing U(G) with the join of an orbit of Qi on Rm(G). For instance, if G = L?(p) for some prime p = ±1 mod (24) one can take r = 1. 10 Finiteness Throughout this paper, we have generally assumed that the group G is finite. If it is not, then not only can RC(G) be infinite, it can even split into infinitely many orbits under the action of QC. Example 10.1 Let C = H+, so that r = F?, and let G = (x,y | x3 = y?), the group ni(S3 \ K) of the trefoil knot K. This group, isomorphic to the three-string braid group B3 = (a, b | aba = bab) with x = ab and y = ab?, has centre Z(G) = (x3) = CTO, with G/Z(G) = C3 * C = PSL?(Z). Dunwoody and Pietrowski [16] have shown that the pairs xj = x3j+i, yj = y?j+i (i G Z) all generate G and lie in different T?-systems. The corresponding normal subgroups N G Nr(G), the kernels of the epimorphisms r ^ G given by X ^ xj, Y ^ yj, therefore all lie in different orbits of the group Q = Out r = GL?(Z), as do the corresponding hypermaps in RC(G). References [1] D. Archdeacon, M. Conder and J. Siran, Trinity symmetry and kaleidoscopic regular maps, Trans. Amer. Math. Soc. 366 (2014), 4491-4512, doi:10.1090/S0002-9947-2013-06079-5. [2] A. J. Breda d'Azevedo and G. A. Jones, Platonic hypermaps, Beiträge Algebra Geom. 42 (2001), 1-37. [3] T. Connor and D. Leemans, An atlas of subgroup lattices of finite almost simple groups, http: //homepages.ulb.ac.be/~tconnor/atlaslat/. [4] T. Connor and D. Leemans, An atlas of subgroup lattices of finite almost simple groups, Ars Math. Contemp. 8 (2015), 259-266. [5] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker and R. A. Wilson, Atlas of finite groups, Oxford University Press, Eynsham, 1985. [6] H. S. M. Coxeter and W. O. J. Moser, Generators and relations for discrete groups, volume 14 of Ergebnisse der Mathematik und ihrer Grenzgebiete [Results in Mathematics and Related Areas], Springer-Verlag, Berlin-New York, 4th edition, 1980. [7] L. E. Dickson, Linear groups: With an exposition of the Galois field theory, with an introduction by W. Magnus, Dover Publications, Inc., New York, 1958. [8] J. D. Dixon, The probability of generating the symmetric group, Math. Z. 110 (1969), 199-205. [9] J. D. Dixon, Asymptotics of generating the symmetric and alternating groups, Electron. J. Combin. 12 (2005), Research Paper 56, 5 pp. (electronic). [10] M. L. N. Downs, Möbius inversion of some classical groups and their application to the enumeration of regular maps, Ph.D. thesis, University of Southampton, Southampton, U.K., 1988. G. A. Jones: Combinatorial categories and permutation groups 239 [11] M. L. N. Downs, The Möbius function of PSL2(q), with application to the maximal normal subgroups of the modular group, J. London Math. Soc. (2) 43 (1991), 61-75, doi:10.1112/jlms/ s2-43.1.61. [12] M. L. N. Downs, The Mobius function of the Suzuki groups, 1993, unpublished preprint. [13] M. L. N. Downs and G. A. Jones, Enumerating regular objects with a given automorphism group, Discrete Math. 64 (1987), 299-302, doi:10.1016/0012-365X(87)90199-3. [14] M. L. N. Downs and G. A. Jones, Mobius inversion in Suzuki groups and enumeration of regular objects, Proc. Math. Statist. (to appear), (Proceedings of SIGMAP 2014, Malvern, 2014). [15] M. J. Dunwoody, On t-systems of groups, J. Austral. Math. Soc. 3 (1963), 172-179. [16] M. J. Dunwoody and A. Pietrowski, Presentations of the trefoil group, Canad. Math. Bull. 16 (1973), 517-520. [17] B. Farb and D. Margalit, A primer on mapping class groups, volume 49 of Princeton Mathematical Series, Princeton University Press, Princeton, NJ, 2012. [18] G. Frobenius, Über Gruppencharaktere, Sitzber. Königlich Preuss. Akad. Wiss. Berlin 1896 (1896), 985-1021. [19] G. Frobenius and I. Schur, Über die reellen Darstellungen der endlichen Gruppen, Sitzber. Königlich Preuss. Akad. Wiss. Berlin 1906 (1906), 186-208. [20] S. Garion and A. Shalev, Commutator maps, measure preservation, and t-systems, Trans. Amer. Math. Soc. 361 (2009), 4631-4651, doi:10.1090/S0002-9947-09-04575-9. [21] E. Girondo and G. Gonzalez-Diez, Introduction to compact Riemann surfaces and dessins d'enfants, volume 79 of London Mathematical Society Student Texts, Cambridge University Press, Cambridge, 2012. [22] A. Grothendieck, Esquisse d'un programme, in: Geometric Galois actions. 1. Around Grothendieck's esquisse d'un programme. Proceedings of the conference on geometry and arithmetic of moduli spaces, Luminy, France, August 1995, Cambridge: Cambridge University Press, pp. 5-48; English translation: 243-283, 1997. [23] R. M. Guralnick and W. M. Kantor, Probabilistic generation of finite simple groups, J. Algebra 234 (2000), 743-792, doi:10.1006/jabr.2000.8357, special issue in honor of Helmut Wielandt. [24] P. Hall, The Eulerian functions of a group, Q. J. Math., Oxf. Ser. 7 (1936), 134-151. [25] I. Hubard and D. Leemans, Chiral polytopes and Suzuki simple groups, in: Rigidity and symmetry, Toronto: The Fields Institute for Research in the Mathematical Sciences; New York, NY: Springer, pp. 155-175, 2014, doi:10.1007/978-1-4939-0781-6_9. [26] L. D. James, Operations on hypermaps, and outer automorphisms, Eur. J. Comb. 9 (1988), 551-560, doi:10.1016/S0195-6698(88)80052-0. [27] G. A. Jones, Ree groups and Riemann surfaces, J. Algebra 165 (1994), 41-62, doi:10.1006/ jabr.1994.1097. [28] G. A. Jones, Enumeration of homomorphisms and surface-coverings, Q. J. Math., Oxf. II. Ser. 46 (1995), 485-507, doi:10.1093/qmath/46.4.485. [29] G. A. Jones, Regular dessins with a given automorphism group, in: Riemann and Klein surfaces, automorphisms, symmetries and moduli spaces, Amer. Math. Soc., Providence, RI, volume 629 of Contemp. Math., pp. 245-260, 2014, doi:10.1090/conm/629/12568. [30] G. A. Jones and D. Pinto, Hypermap operations of finite order, Discrete Math. 310 (2010), 1820-1827, doi:10.1016/j.disc.2009.12.019. [31] G. A. Jones and A. Poulton, Maps admitting trialities but not dualities, Eur. J. Comb. 31 (2010), 1805-1818, doi:10.1016/j.ejc.2010.02.001. 61 Ars Math. Contemp. 10 (2016) 393-410 [32] G. A. Jones and S. A. Silver, Suzuki groups and surfaces, J. Lond. Math. Soc., II. Ser. 48 (1993), 117-125, doi:10.1112/jlms/s2-48.1.117. [33] G. A. Jones and J. S. Thornton, Operations on maps, and outer automorphisms, J. Comb. Theory, Ser.B 35 (1983), 93-103, doi:10.1016/0095-8956(83)90065-5. [34] G. A. Jones and J. S. Thornton, Automorphisms and congruence subgroups of the extended modular group, J. Lond. Math. Soc., II. Ser. 34 (1986), 26-40, doi:10.1112/jlms/s2-34.1.26. [35] W. M. Kantor and A. Lubotzky, The probability of generating a finite classical group, Geom. Dedicata 36 (1990), 67-87, doi:10.1007/BF00181465. [36] M. W. Liebeck and A. Shalev, The probability of generating a finite simple group, Geom. Dedicata 56 (1995), 103-113, doi:10.1007/BF01263616. [37] S. Lins, Graph-encoded maps, J. Comb. Theory, Ser. B 32 (1982), 171-181, doi:10.1016/ 0095-8956(82)90033-8. [38] R. C. Lyndon and P. E. Schupp, Combinatorial group theory, Berlin: Springer, reprint of the 1977 ed. edition, 2001. [39] A. Machi, On the complexity of a hypermap, Discrete Math. 42 (1982), 221-226, doi:10.1016/ 0012-365X(82)90219-9. [40] W. Magnus, A. Karrass and D. Solitar, Combinatorial group theory. Presentations of groups in terms of generators and relations, Mineola, NY: Dover Publications, reprint of the 1976 second edition edition, 2004. [41] A. Maroti and M. Tamburini, Bounds for the probability of generating the symmetric and alternating groups, Arch. Math 96 (2011), 115-121, doi:10.1007/s00013-010-0216-z. [42] A. Mednykh, Determination of the number of nonequivalent coverings over a compact Riemann surface, Sov. Math Dokl. 19 (1978), 318-320. [43] J. R. Munkres, Topology, Upper Saddle River, NJ: Prentice Hall, 2nd edition, 2000. [44] R. Nedela and M. Skoviera, Exponents of orientable maps, Proc. Lond. Math. Soc. (3) 75 (1997), 1-31, doi:10.1112/S0024611597000245. [45] B. H. Neumann and H. Neumann, Zwei Klassen charakteristischer Untergruppen und ihre Faktorgruppen, Math. Nachr. 4 (1951), 106-125, doi:10.1002/mana.19500040112. [46] J. Nielsen, Die Isomorphismen der allgemeinen, unendlichen Gruppe mit zwei Erzeugenden, Math. Ann. 78 (1917), 385-397, doi:10.1007/BF01457113. [47] R. B. Richter, J. Siran and Y. Wang, Self-dual and self-Petrie-dual regular maps, J. Graph Theory 69 (2012), 152-159, doi:10.1002/jgt.20570. [48] J.-P. Serre, Topics in Galois theory. Notes written by Henri Darmon, Wellesley, MA: A K Peters, 2nd edition, 2007. [49] J. Siran, How symmetric can maps on surfaces be?, in: Surveys in combinatorics 2013. Papers based on the 24th British combinatorial conference, London, UK, June 30 - July 5, 2013, Cambridge: Cambridge University Press, pp. 161-238, 2013. [50] M. Suzuki, On a class of doubly transitive groups, Ann. Math. (2) 75 (1962), 105-145, doi: 10.2307/1970423. [51] T. R. S. Walsh, Hypermaps versus bipartite maps, J. Comb. Theory, Ser. B 18 (1975), 155-163, doi:10.1016/0095- 8956(75)90042- 8. [52] R. A. Wilson, The finite simple groups, London: Springer, 2009, doi:10.1007/ 978-1-84800-988-2. [53] S. E. Wilson, Operators over regular maps, Pac. J. Math. 81 (1979), 559-568, doi:10.2140/pjm. 1979.81.559.