GROUP ACTIONS ON GRAPHS, MAPS AND SURFACES WITH MAXIMUM SYMMETRY

MARSTON CONDER

Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand

Abstract

This is a summary of a short course of lectures given at the Groups St Andrews conference in Oxford, August 2001, on the significant role of combinatorial group theory in the study of objects possessing a high degree of symmetry. Topics include group actions on closed surfaces, regular maps, and finite s-arc-transitive graphs for large values of s. A brief description of the use of Schreier coset graphs and computational methods for handling finitely-presented groups and their images is also given.

1 Introduction

Historically there has been a great deal of fascination with symmetry — in art, science and culture. One of the key strengths of group theory comes from the use of groups to measure and analyse the symmetries of objects, whether these be physical objects (in 2 or 3 dimensions), or more purely mathematical objects such as roots of polynomials or vectors or indeed other groups. This is now bearing unexpected fruit in areas such as structural chemistry (with the study of fullerenes for example), and interconnection networks (where Cayley graphs and other graphs constructed from groups often have ideal properties for communication systems).

The aim of this paper (and the associated short course of lectures given at the Groups St Andrews 2001 conference in Oxford) is to describe a number of instances of symmetry groups of mathematical objects where the order of the group is as large as possible with respect to the genus, size or type of the object. Topics covered include Hurwitz groups (maximum order conformal automorphism groups of compact Riemann surfaces), regular maps (embeddings of graphs in surfaces having automorphism group transitive on incident vertex-edge-face triples), and finite symmetric graphs with automorphism group acting transitively on directed non-reversing walks of length s for the highest possible values of s. In each case combinatorial group theory plays a significant role, and accordingly, a brief description of the use of some graphical and computational methods for handling finitely-presented groups and their images is also given.

Please note that this paper makes no claims to be a comprehensive survey of the theme of maximum symmetry, or even of each of the topics dealt with. It is hoped, however, that the paper will provide some of the flavour of research in this field, through description of a range of recent discoveries, and a good deal of references.

The paper is organised as follows. In Section 2, we describe some of the tools that have proved useful to the author and others in this area, including the low index subgroups process and Schreier coset graphs. Section 3 deals with automorphism groups of compact Riemann surfaces, with particular reference to Hurwitz groups. Section 4 concerns regular maps, on both orientable and non-orientable surfaces, and goes on to describe some recent work on the maximum number of automorphisms of a closed non-orientable surface of given genus. In Section 5 we consider finite graphs with large symmetry groups, concentrating on the special cases of 5-arc-transitive and 7-arc-transitive graphs of valency 3 and 4 respectively. Finally, Section 6 describes two instances where unexpected results have arisen, and Section 7 lists a number of open problems.

A number of definitions will be useful background for the material which follows. A surface will be taken as a closed 2-manifold without boundary. The (topological) genus of an orientable surface is the number of ‘handles’ attached to a sphere to obtain it, and is related to the Euler characteristic by the formula χ = 2 − 2g (where g is the genus); for example, the sphere has genus 1, the torus has genus 2, the double torus has genus 3, etc. Analogously, the genus g of a non-orientable surface is the number of its ‘cross-caps’, and is related to the Euler characteristic by the formula χ = 2 − g; for example, the real projective plane has genus 1, and the Klein bottle has genus 2.

A graph is a combinatorial network, consisting of a pair (V, E) where V is a set (of vertices) and E is an irreflexive symmetric relation on V (that is, a set of unordered pairs of distinct vertices (called edges)). As such, graphs in this context are simple, with undirected edges, no loops and no multiple edges. A multigraph is a generalisation of a graph, in which multiple edges are allowed between any pair of distinct vertices. Finally, a map is a 2-cell embedding of a connected graph or multigraph into a surface (so that the connected components of the complementary space obtained by removing the graph or multigraph from the surface are all homeomorphic to open disks, called faces).

2 Methods for dealing with finitely-presented groups

2.1 Computational algorithms

Several efficient computational procedures have been developed over the last four decades for handling abstract groups with a small number of generators and defining relations, and have been implemented in computer support packages such as Magma and GAP. Very briefly, for a finitely-presented group G = ⟨X | R⟩ these include the following:

(a) Coset enumeration: variants of a method due to Todd and Coxeter may be used to attempt to determine the index of a finitely-generated subgroup H in G;

(b) Low index subgroups: algorithms (developed principally by Sims) enable the determination of a representative of each conjugacy class of subgroups of up to some specified index N in G; (c) Reidemeister-Schreier rewriting process: this gives a defining presentation for a subgroup H of finite index in G, in terms of Schreier generators;

(d) Abelian quotient algorithm: this can produce the direct factors of the abelianisation H/[H, H] of a subgroup H of finite index in G;

(e) p-quotient and nilpotent quotient algorithms: these produce p-quotients or nilpotent quotients (respectively) of G, of up to a given nilpotency class.

Excellent descriptions of these may be found in the book by Charles Sims [51].

2.2 Low index subgroups

The low index subgroups algorithm is especially important in the computational study of small finite images of finitely-presented groups. The basic algorithm (due to Sims) finds a representative of each conjugacy class of subgroups of index up to some specified N in a given finitely-presented group G = ⟨X | R⟩. This involves a backtrack search through a tree, with nodes at level k in the tree corresponding to (pseudo)subgroups generated by k elements. The search begins (at level 0) with the identity subgroup, generated by the empty set, and successively adjoins and removes elements to and from the generating set for the subgroup, on a last-in first-out basis.

At each stage of the search, coset enumeration is used to define sufficiently many right cosets of the current subgroup H, and to construct a (possibly partial) coset table for H, with rows indexed by the cosets, and columns indexed by elements of the generating set X and their inverses. This table indicates as far as possible the effect of right multiplication of each generator of G on those right cosets of H which have been defined. Definition of cosets is assumed to follow a systematic pattern, sometimes called normal ordering, so that to each subgroup H of finite index in G there exists exactly one coset table in normal order.

In the coset enumeration procedure, definition of new cosets alternates with testing current definitions of coset numbers using the given relators for G and current generators for the (pseudo)subgroup H, and processing of any coincidences that arise. If the definitions satisfy simultaneously all tests against the relators and subgroup generators, and more than the required number of cosets have been defined, then cosets may be forced to coincide. Accordingly, branches are created to new nodes at the next level of the search tree by identifying pairs of cosets: forcing Hw_{i} = Hw_{j} is equivalent to adjoining w_{i}w_{j}^{−1} to a set of generators for H (and therefore moving to the next level).

If at any node, every entry in the coset table is filled, then the coset table is said to be closed, and a subgroup has been found. Tests are built in to avoid generating the same subgroup more than once (by rejecting sub-trees) and also to avoid conjugates of subgroups found earlier in the search tree (isomorph rejection). The algorithm stops when the whole search tree has been traversed.

Example 2.1 The LowIndexSubgroups command in Magma can find the 45991 classes of subgroups of index 120 in the Coxeter group [4, 3, 5] in less than 2 hours on a 400MHz processor.

The low index subgroups algorithm may be combined with the Reidemeister-Schreier process or cohomological methods (applied to the subgroup of finite index or its core) to prove that a given finitely-presented group G is infinite, or to find lower bound on its order, or to prove a given subgroup has infinite index. Numerous examples exist in the literature (for example [37]) and in documentation for Magma and GAP. Also clearly the algorithm can be used to determine all finite factor groups of G isomorphic to permutation groups of small degree (from right representations of G on cosets of subgroups H). This can be particularly helpful in a search for small concrete examples of such factor groups, which can then be used as building blocks for larger examples, as will be seen later.

Another important observation to make about the low index subgroups algorithm is that distinct sub-trees can be processed independently. This provides a basis for distributed processing or parallelisation, of either the basic algorithm or special adaptations.

One such adaptation involves pursuing only selected branches of the search tree: for example those which correspond to subgroups avoiding a given set of elements (and their conjugates). This has applications to searching for torsion-free subgroups of finite index, or subgroups complementary to a given finitely-generated subgroup.

Example 2.2 Spherical and hyperbolic 3-manifolds tessellated by regular solids are obtainable by identifying faces of regular solids of type {p, q, r}. A complete classification of these was obtained by Brent Everitt in his PhD thesis [35], using the observation that a typical cell Δ is a fundamental region for a subgroup complementary to the cell-stabilizer [p, q] in the Coxeter group [p, q, r].

A similar approach was taken earlier in [18] to find torsion-free subgroups of minimum index in particular groups which produce hyperbolic 3-manifolds and orbifolds of minimal volume, and the potential exists for further applications in geometric situations where such subgroups or complements of a given finitely-generated subgroup need to be determined.

2.3 Low index normal subgroups

Another straightforward but significant adaptation of the low index subgroups algorithm finds all normal subgroups of up to a specified index N in a finitely presented group G = ⟨X | R⟩, and hence can produce all finite factor groups G/K of G of order at most N.

Such an adaptation of the standard low index subgroups algorithm is easy: when a coincidence between cosets Ku and Kv of the current subgroup K is forced in the branching process, all conjugates of the element uv^{−1} must lie in K if K is to be normal; hence in the coincidence processing and subsequent coset enumeration phases the element uv^{−1} should be applied to all cosets currently active (and not just the trivial coset numbered “1”). In other words, the element uv^{−1} is treated as an additional relator rather than an additional subgroup generator. The search still begins (at level 0) with the identity subgroup, generated by the empty set, but then successively adjoins and removes elements to and from a set of representatives of conjugacy classes of G which generate the normal subgroup K, again on a last-in first-out basis.

This adaptation not only reduces the coset table more than a forced coincidence in the standard procedure at each stage, but also takes appreciably less time than finding all classes of subgroups of index up to N and eliminating those which are not normal. This in turn enables a search up to much higher index (within given computing resources). The reduction in computing time can be spectacular:

Example 2.3 The modular group PSL_{2}(ZZ) has an abstract defining presentation ⟨ x, y | x^{2} = y^{3} = 1 ⟩ in terms of linear fractional transformations x : z ↦ −1/z and y : z ↦ (z −1)/z, and is thus isomorphic to a free product C_{2} ∗C_{3} of cyclic groups of orders 2 and 3. One way of finding all normal subgroups of index up to (say) 20 in this group is to apply the standard low-index subgroups algorithm and check each subgroup in the output for normality (using a conjugacy test), deleting all subgroups which are non-normal. On a 225Mhz processor, the standard algorithm takes about 2 minutes to find conjugacy class representatives of all subgroups of up to index 20, while the normal subgroups adaptation described above takes only 0.05 seconds to find all normal subgroups up to the same index.

A parallel implementation of the low index subgroups algorithm (and its normal subgroups adaptation) was developed by Peter Dobcsányi as part of his PhD thesis project [34]. Called Lowx, this implementation is capable of running on many parallel hardware platforms, but its most important use to date has been on Kaláka, a 170-node Linux cluster which he designed and built using machines in student computer laboratories during their idle time. This provided equivalent computing power to a medium-sized supercomputer, at a fraction of the cost! Applications will be described in Sections 4.5 and 5.2.

2.4 Schreier coset graphs

If G is a group with finite generating-set X = {x_{1}, x_{2}, …, x_{d}}, and H is a subgroup of index n in G, then the Schreier coset graph Σ(G, X, H) is the graph with vertices labelled by the right cosets of H, and with all edges of the form Hg — Hgx_{i} for 1 ≤ i ≤ d. This graph provides a diagrammatic representation of the action of G on cosets of H by right multiplication.

Similarly, if G has a transitive permutation representation on a set Ω of size n, then we may form a graph with vertices as the points of Ω and with all edges of the form α — α^{x_{i}} for 1 ≤ i ≤ d; this is naturally isomorphic to the coset graph for G associated with the point-stabilizer H = G_{α} = {g ∈ G : α^{g} = α}. In fact these things are essentially interchangeable: the coset table, the coset graph, and permutations induced by the group generators. See [29] for many examples.

A number of observations are worth making about Schreier coset graphs. First, any path in the graph may be traced using a word w = w(X) in the generators of G, and elements of the subgroup H expressed as words in the generators of G correspond to directed circuits in the coset graph based at the vertex labelled H.

Next, a Schreier transversal for H in G corresponds to a spanning tree for the coset graph: any path in a spanning tree based at the vertex H may be traced by a word w, the initial sub-words of which correspond to initial sub-paths of the given path. It follows that a Schreier generating-set for H in G corresponds to the set of edges of the coset graph not used in a spanning tree. For example, the broken edge in Figure 1 completes a circuit corresponding to the Schreier generator ux_{i}v^{−1}:

PSfrag replacements

H
Hu

Hv = Hux_{i}

Figure 1. Schreier generators given by edges not in the spanning tree

These observations may be taken further, leading to a diagrammatic interpretation (and implementation) of the Reidemeister-Schreier process: to find a presentation for a subgroup H of finite index in a finitely-presented group G = ⟨X | R⟩, one can simply take a spanning tree in the coset graph Σ(G, X, H), label the unused edges with Schreier generators, and then apply the relators in R to each of the vertices in turn to obtain the relations.

Schreier coset graphs have other theoretical applications, for example to the following theorem which provides a necessary condition for transitivity of a group generated by a set of permutations (due independently to Ree and Singerman): If G is the group generated by permutations x_{1}, x_{2}, …, x_{d} on a set Ω of size n, such that x_{1}x_{2} … x_{d} = 1, and c_{i} is the number of orbits of ⟨x_{i}⟩ on Ω, then G is transitive on Ω only if c_{1} + c_{2} + … + c_{d} ≤ (d − 2)n + 2. This can be proved by taking a particular embedding [11] of the associated coset graph in an orientable surface of genus g ≥ 0, counting the numbers V, E and F of vertices, edges and faces (respectively), and then applying Euler’s formula 2 − 2g = χ = V − E + F.

Coset graphs can also have important more practical applications. In some cases, copies of the same coset graph for a group G may be joined together to construct permutation representations of G of arbitrarily large degree, showing in particular that the group is infinite. (This is related to abelianisation of the Reidemeister-Schreier process, but will not be pursued in detail here.)

In other cases, two coset graphs for a given finitely-presented group G = ⟨X | R⟩ which contain a fixed point of the same involutory generator (in X) can often be joined together by the insertion of an extra transposition which interchanges those two points, to produce a transitive permutation representation of G of larger degree. Necessary conditions are imposed by the relations, however the effect of such composition of coset graphs on each relator (or any other word in the group generators) can be seen by ‘diagram chasing’, and/or using the fact that multiplication of a given permutation by a single transposition (α, β) always either splits a cycle (containing both α and β) or concatenates two different cycles (containing α and β separately).

This method of composition of coset graphs was developed by Graham Higman in proving that for all sufficiently large n, the alternating group A_{n} is a homomorphic image of the (2, 3, 7) triangle group Δ = ⟨ x, y, z | x^{2} = y^{3} = z^{7} = xyz = 1 ⟩.

Higman observed that every coset graph for this group Δ may be drawn very simply, with small triangles and heavy dots representing 3-cycles and fixed points of the permutation induced by the generator y, connected together by straight or curved lines representing 2-cycles of the permutation induced by the generator x. By convention, the vertices of each small triangle may be assumed to be permuted anti-clockwise by y, and loops representing fixed points of x are omitted. Cycles of the element xy (= z^{−1}) of order 7 can be traced around ‘faces’ of the drawing.

If two such coset graphs both involve 7-cycles of xy which contain two fixed points of x separated in the cycle by the same number of points (either 1, 2 or 3 points), then the two coset graphs may be composed together by introducing new transpositions for x, interchanging the corresponding points.

In the first case, if one has a 7-cycle (a, b, c_{1}, c_{2}, c_{3}, c_{4}, c_{5}) for xy in which a and b are fixed by x, and the other has a similar 7-cycle (a′, b′, c′_{1}, c′_{2}, c′_{3}, c′_{4}, c′_{5}), then introducing two new 2-cycles (a, a′) and (b, b′) to the permutation induced by x gives rise to a larger coset graph in which (a, b′, c_{1}, c_{2}, c_{3}, c_{4}, c_{5}) and (a′, b, c′_{1}, c′_{2}, c′_{3}, c′_{4}, c′_{5}) are 7-cycles of xy. Other cycles of xy (and of y and x) are unaffected, hence the resulting graph is indeed a coset graph for the (2, 3, 7) triangle group Δ. This and the other two possibilities (which are similar) are illustrated in Figure 2.

Figure 2. Composition of coset graphs for the (2, 3, 7) triangle group

Interesting things can happen when coset graphs are linked together in this way. For example, the (2, 3, 7) triangle group has permutation representations of degrees 14, 64 and 22 in which the groups generated by the permutations are isomorphic to PSL_{2}(13), A_{64} and A_{22} respectively. The corresponding coset graphs can be composed to create a transitive permutation representation of degree 100, in which the permutations generate the Hall-Janko simple group J_{2}, of order 604800.

Another representation as PSL_{2}(13) on 42 points has three cycles of xy available for Higman’s composition technique, and copies of the coset graph can be linked together in a circuit to produce permutations which generate extensions by PSL_{2}(13) of an abelian group of any given exponent.

The cycle structure of the commutator [x, y] in the latter representation is 1^{3}13^{3}. This coset graph can be composed with another coset graph for Δ on 36 points, in which the commutator [x, y] has cycle structure 1^{1}4^{2}5^{1}11^{2}, so that in the resulting transitive permutation representation of Δ on 78 points, the commutator [x, y] has cycle structure 1^{4}4^{2}5^{1}11^{1}12^{2}13^{2}. In particular, by choice of representations, each of the unique 5- and 11-cycles of [x, y] contains points α and β such that α^{x} = α and α^{y} = β. Now if B were a block of imprimitivity containing α, then B would be preserved by the 11-cycle [x, y]^{780}, but then B would be preserved by x (as α^{x} = α ∈ B) and by y (as α^{y} = β ∈ B), forcing |B| = 78, and hence the action must be primitive. By Jordan’s theorem (on primitive groups containing prime-length cycles) [58], it follows that the permutations generate A_{78}.

Chains of additional copies of the coset graph on 42 points and/or one or two of the graph on 14 points mentioned earlier can also be joined to the first (on 42 points), to prove that the alternating group A_{n} is a homomorphic image of Δ for all n of the form 14k + 78 with k ≥ 0. Similarly other coset graphs of various shapes and sizes can be tacked on, to prove the following refinement of Higman’s theorem [9], published by the author in 1980:

Theorem 2.1 The alternating group A_{n} is a homomorphic image of the (2, 3, 7) triangle group, for all n ≥ 168.

Incidentally, this has been taken much further recently by Higman’s academic grandson, Brent Everitt, who has proved in [36] that a similar result holds not only for every hyperbolic (p, q, r) triangle group ⟨ x, y, z | x^{p} = y^{q} = z^{r} = xyz = 1 ⟩ with 1/p + 1/q + 1/r < 1, but also for every Fuchsian group (see Section 3.1):

Theorem 2.2 Every Fuchsian group has all but finitely many alternating groups A_{n} among its homomorphic images.

3 Automorphism groups of compact Riemann surfaces

3.1 Hurwitz’s theorem

The theory of Riemann surfaces is very well-developed, and described nicely in a book by Jones and Singerman on complex functions [39].

A Riemann surface is a connected 2-manifold endowed with a complex analytic structure (called an atlas) that allows local coordinatisation — somewhat analogous to a book of maps of the planet Earth. An automorphism of a Riemann surface X is a homeomorphism f : X → X which preserves the local analytic structure. As usual, automorphisms form a group under composition, known as the automorphism group of X and denoted by Aut X.

A Riemann surface X may also be identified with the orbit space U/Λ of the action of a normal subgroup Λ of finite index in some discrete subgroup Γ of the group PSL_{2}(IR), acting on the upper-half complex plane U. The quotient group Γ/Λ is then isomorphic to the automorphism group Aut X.

Associated with the action of the discrete group Γ on U is a fundamental region D = D(Γ): this is a closed set whose images under Γ have disjoint interiors and cover the whole of U.

If the Riemann surface X = U/Λ is compact, then a fundamental region for Γ has finitely many sides. In this case the group Γ has a finite presentation in terms of elliptic generators X_{1}, X_{2}, …, X_{r} and hyperbolic generators A_{1}, B_{1}, …, A_{γ}, B_{γ} (where γ is called the underlying genus, determined by Λ), and subject to defining relations X_{1}^{m_{1}} = X_{2}^{m_{2}} = … = X_{r}^{m_{r}} = 1 and X_{1}X_{2} … X_{r} [A_{1}, B_{1}] … [A_{γ}, B_{γ}] = 1. Such a discrete group Γ is called a Fuchsian group, and is said to have signature (γ; m_{1}, m_{2}, …, m_{r}). The parameters m_{i} are the orders of branch points.

The area μ(D) of the fundamental region D = D(Γ) is given by the formula μ(D) = 2π (2γ − 2 + ∑_{i=1}^{r}(1 − 1/m_{i}) ). The celebrated Riemann-Hurwitz formula states that |Γ/Λ| = \frac{2π(2g−2)}{μ(D)}, where g is the topological genus of the surface X, and this easily converts to the more customary form of

2g − 2 = |Aut X| (2γ − 2 + ∑_{i=1}^{r}(1 − 1/m_{i}) ).

The bracketed expression has minimum positive value of \frac{1}{42}, which is attained precisely when γ = 0, r = 3 and {m_{1}, m_{2}, m_{3}} = {2, 3, 7}. This leads to:

Theorem 3.1 (Hurwitz, 1893) If X is a compact Riemann surface of genus g > 1, then |Aut X| ≤ 84(g − 1), and moreover, the upper bound on this order is attained if and only if Aut X is a homomorphic image of the (2, 3, 7) triangle group Δ = ⟨ X, Y, Z | X^{2} = Y^{3} = Z^{7} = XY Z = 1 ⟩.

Because of this theorem, non-trivial finite quotients of the (2, 3, 7) triangle Δ are known as Hurwitz groups.

3.2 Hurwitz groups

Every Hurwitz group G is perfect (that is, G coincides with its commutator subgroup G′), since abelianisation of the (2, 3, 7) relations gives 1 = z^{−7} = (xy)^{7} = x^{7}y^{7} = xy and so x = y^{−1}, which implies x and y are both trivial. It follows that every Hurwitz group has a nonabelian simple quotient, and hence it is natural to look among the nonabelian simple groups for examples of Hurwitz groups.

In the 1960s Murray Macbeath [45] used matrix and number-theoretic arguments to prove that the projective special linear group PSL_{2}(q) is Hurwitz if and only if • q = 7, or

• q = p for some prime p ≡ ±1 mod 7, or

• q = p^{3} for some prime p ≡ ±2 or ±3 mod 7.

As noted earlier (in Section 2.4), the author of this paper used Graham Higman’s method of composition of coset graphs to prove in [9] that the alternating group A_{n} is Hurwitz for all n ≥ 168 (and for all but 64 smaller values of n as well).

Several other simple groups (and families of simple groups) have been shown to be Hurwitz using character-theoretic techniques. In any finite group G with known character table, the number of pairs (x, y) of elements such that x has order 2, y has order 3, and xy has order 7 can be calculated using the structure constants

c_{ijk} = \frac{|K_{i}||K_{j}||K_{k}|}{|G|} ∑_{χ∈Irr(G)} \frac{χ(g_{i})χ(g_{j})χ(g_{k})}{χ(1)}

where K_{i}, K_{j} and K_{k} denote conjugacy classes of elements of orders 2, 3 and 7, and χ(g_{r}) is the value of the irreducible character χ on a representative g_{r} of the conjugacy class K_{r}. Good knowledge of the maximal subgroup structure and local analysis can often be used to account for subgroups generated by these pairs, and hence to determine whether or not G itself is so generated. (In fact by Philip Hall’s theory of Möbius inversion on lattices, all one needs to know are the numbers of pairs that lie in intersections of maximal subgroups; see [41]).

Chih-han Sah proved in [50] that certain Ree groups ^{2}G_{2}(3^{e}) are Hurwitz, and Gunter Malle later showed that ^{2}G_{2}(3^{e}) is Hurwitz for all odd e > 1 (see [47], and [40]). Also Malle proved that the Chevalley groups G_{2}(q) are Hurwitz for all q > 4, as well as the twisted simple groups ^{3}D_{4}(q) for all q ≠ 4 or 3^{s} (for any s) and ^{2}F_{4}(2^{2n+1})′ for all n ≡ 1 mod 3 (see [47, 48]).

Particular attention has been paid to the sporadic simple groups in this context. In a series of papers in the 1990s by Rob Wilson and Andy Woldar and the author (whose involvement was relatively minor), it has been established that exactly 12 of the 26 sporadic finite simple groups are Hurwitz. The final (and most spectacular) step in this process was the very recent proof by Rob Wilson [59] that the Monster can be generated by two elements of orders 2 and 3 whose product has order 7, as a result of some highly innovative computational approaches to investigating subgroups of the Monster using its 196882-dimensional representation over GF(2). In particular, the Monster is a group of automorphisms of some compact Riemann surface X for which equality is attained in the upper bound on |Aut X| given by Hurwitz’s theorem. (It is also the orientation-preserving subgroup of the group of automorphisms of a regular map on a surface of the same genus; see Section 4.)

The sporadic simple groups which are Hurwitz are now known to be J_{1}, J_{2}, He, Ru, Co_{3}, F i_{22}, HN, Ly, T h, J_{4}, F i′_{24} and the Monster M. The other 14 sporadic finite simple groups are not Hurwitz (although many of them can still be generated by two elements of orders 2 and 3).

Also recently, Andrea Lucchini, Chiara Tamburini and John Wilson have taken a different approach to show that ‘most’ finite simple classical groups of sufficiently large dimension are Hurwitz groups [43, 44]. In fact what they prove in [44] is that if R is any finitely-generated ring with at least one generator t having the property that 2t − t^{2} is a unit of finite multiplicative order, and E_{n}(R) is the group of invertible n × n matrices generated by the set { I_{n} + re_{ij} | r ∈ R, 1 ≤ i ≠ j ≤ n } of elementary transvections, then E_{n}(R) can be generated by two matrices X and Y such that X^{2} = Y^{3} = (XY)^{7} = 1, for all but finitely many n. The proof uses the permutation matrices corresponding to Hurwitz generators for the alternating group A_{n} (as provided in [9]), with modification of the generator of order 2 in order to obtain E_{n}(R). Similar methods are applied in [43].

As a consequence of this work by Lucchini, Tamburini and Wilson, the following are Hurwitz groups, in addition to many others:

• the special linear group SL_{n}(q) for all n ≥ 287 and every prime-power q;

• the symplectic group Sp_{2n}(q) for all n ≥ 371 and all q;

• the orthogonal groups Ω_{2n}^{+}(q) for all q and Ω_{2n+7}(q) for all odd q, for n ≥ 371;

• the unitary groups SU_{2n}(q) for all q and SU_{2n+7}(q) for all odd q, for n ≥ 371. In particular, the simple projective quotients of these groups are all Hurwitz

also; hence for example, PSL_{n}(q) is a Hurwitz group for all n ≥ 287 and every prime-power q. In addition, it follows from the main theorem of [44] and previous work by John Wilson that there are 2^{ℵ_{0}} infinite simple groups which are factor groups of the (2, 3, 7) triangle group.

Next, we note that there are several ways of constructing larger Hurwitz groups from given examples. Such constructions include direct products of Hurwitz groups (with different presentations), semi-direct products (of abelian groups by simple Hurwitz groups for example), and central products (of special linear groups for example). Some of these were described in the author’s determination of all Hurwitz groups of order up to 1 million [10] and in his survey article [15].

The central product construction can also be applied to the (2, 3, 7)-generation of SL_{n}(q) to show that the centre of a Hurwitz group can be any finite abelian group, fully answering a question posed by John Leech in the 1960s (see [27]).

Finally, we note some non-existence results. Jeffrey Cohen [8] showed in 1981 that PSL_{3}(q) is Hurwitz only when q = 2, and hence the same holds for SL_{3}(q). Very recently, Di Martino, Tamburini and Zalesskii proved that many other linear groups of small degree are not Hurwitz, including SL_{n}(q) and SU_{n}(q^{2}) for several n ≤ 19 and various q (see [31]), using Leonard Scott’s matrix group analogue of the Ree-Singerman theorem on a necessary condition for generation by a given subset.

4 Regular maps

4.1 Definitions and background

Regular maps may be viewed as generalisations of the Platonic solids. As defined earlier, a map is a 2-cell embedding of a connected graph (or multigraph) into a closed surface without boundary. Such a map M is composed of a vertex-set V = V (M), an edge-set E = E(M), and a set of faces which we will denote by F = F (M). The map is orientable or non-orientable according to whether the underlying surface (on which the graph is embedded) is orientable or non-orientable.

The faces of M are the simply-connected components of the complementary space obtained by removing the embedded graph from the surface; alternatively, in the orientable case, they can be defined more directly by considering just the underlying graph together with a ‘rotation’ at each vertex (see [38] or [60]).

Associated also with any map is a set of darts (or arcs), which are the incident vertex-edge pairs (v, 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 much 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. From connectedness of the underlying graph, it follows that every automorphism is uniquely determined by its effect on any blade, and hence the number of automorphisms of M is bounded above by the number of blades, or equivalently, |Aut M| ≤ 4|E|.

Now if there exist automorphisms 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 edges incident to some vertex v of f (in single steps around v), then following Steve Wilson [60] we may call M a rotary map. Under more currently accepted terminology, M is also called a regular map (in the sense of Brahana, who generated early interest [2] in such objects in the 1920s). In this case, again by connectedness, Aut M acts transitively on vertices, on edges, and on faces of the map M, and it follows that M is combinatorially regular, with all its faces bordered by the same number of edges, say p, and all its vertices having the same degree, say q. The pair {p, q} is known as the type of the map M.

(Note that the converse does not hold: a map can be combinatorially regular without being regular; indeed coset graphs for the (2, 3, 7) triangle group can be used to prove [20] that for every g > 1 there exists a combinatorially regular map of type {3, 7} on an orientable surface of genus g, with trivial automorphism group.)

When M is rotary, R and S may be chosen (by replacing one of them by its inverse if necessary) so 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.

PSfrag replacements

v
e
f
R
S
a

Figure 3. Local action associated with a blade (v, e, f) in a regular map

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 regular map M is reflexible. This automorphism a is may be thought of geometrically as a reflection, about an axis passing through the midpoints of the edge e and the face f. Similarly, the automorphisms b = aR and c = 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. In this case, Aut M is transitive (indeed regular) on blades, and can be generated by the three reflections a, b and c.

If the map M is orientable, then the elements R = ab and S = bc generate a normal subgroup of index 2 in Aut M, consisting of all elements expressible as a word of even length in {a, b, c}, called the rotation subgroup Aut^{+}M. In this case the elements of Aut^{+}M are precisely those automorphisms which preserve the orientation of the underlying surface, while all those in Aut M \ Aut^{+}M are orientation-reversing. In the non-orientable case, however, there are no true reflections: every ‘reflection’ is a product of rotations. In particular, each of a, b and c is expressible as a word in the rotations R and S, and hence ⟨R, S⟩ = ⟨ab, bc⟩ has index 1 in Aut M.

On the other hand, if no such automorphism a exists, then the rotary map M is called chiral, and its automorphism group is generated by the rotations R and S. Chiral maps are necessarily orientable. Also chiral maps occur in opposite pairs, with one member of each pair obtainable from the other by reflection.

Further details and some historical background may be found in [29, 38, 60].

4.2 Genus calculation

The genus of a map M is defined as the genus of the surface on which M is embedded, and is given by the usual formula in terms of the Euler characteristic:

χ(M) = |V | − |E| + |F | = \{ \begin{matrix}2 − 2g & if M is orientable \\ 2 − g & if M is non-orientable. \end{matrix}

For regular maps of type {p, q}, counting the number of blades containing a given edge e yields |Aut M| = 2|E| if the rotary map M is chiral, or |Aut M| = 4|E| when M is reflexible. Also in both cases, counting the number of darts incident with a given vertex, edge or face gives q|V | = 2|E| = p|F |. These together with the formula above make the calculation of the genus straightforward:

g = g(M) = \{ \begin{matrix}|Aut M|(1/8 − 1/4p − 1/4q) + 1 & if M is orientable and reflexible \\ |Aut M|(1/4 − 1/2p − 1/2q) + 1 & if M is orientable but chiral \\ |Aut M|(1/4 − 1/2p − 1/2q) + 2 & if M is non-orientable. \end{matrix}

As similarly observed for Hurwitz’s theorem, in all cases the bracketed expression attains its smallest positive value when {p, q} = {3, 7}, and thus regular maps of types {3, 7} and {7, 3} have the largest possible symmetry groups. Indeed:

Theorem 4.1 If X is a reflexible regular map of genus g > 1, then

|Aut X| ≤ \{ \begin{matrix}168(g − 1) & if M is orientable \\ 84(g − 2) & if M is non-orientable, \end{matrix}

and moreover, the upper bound on this order is attained if and only if Aut X is a homomorphic image of the extended (2, 3, 7) triangle group ⟨ A, B, C | A^{2} = B^{2} = C^{2} = (AB)^{2} = (BC)^{3} = (CA)^{7} = 1 ⟩.

Note that the topological dual of a regular map M, denoted by M^{∗} and obtainable by taking V (M^{∗}) = F (M), E(M^{∗}) = E(M) and F (M^{∗}) = V (M) and the same relations of incidence, will also be regular, with the same automorphism group as M, and of type {q, p}. Hence types {3, 7} and {7, 3} are equivalent. Similarly the orders 2, 3 and 7 of the pairwise products AB, BC and CA in the above presentation for the extended (2, 3, 7) triangle group can be permuted among themselves while still defining the same group.

4.3 Group theoretic construction of regular maps

In the background analysis described in Section 4.1, the three reflections a, b and c generating the automorphism group of a regular map M were chosen so that with respect to the given blade (v, e, f), the automorphism a stabilises the edge e and the face f but moves the vertex v, while b = aR fixes v and f but moves e, and c = aRS fixes v and e but moves f. Accordingly, V = ⟨b, c⟩ is the stabilizer in G = Aut M of the vertex v, while E = ⟨a, c⟩ is the stabilizer in G of the edge e, and F = ⟨a, b⟩ is the stabilizer in G of the face f. Also vertices, edges and faces of M can be identified with (right) cosets of these subgroups V, E and F, with incidence corresponding to non-trivial intersection.

This background theory can be exploited to produce a purely group-theoretic method of construction of examples of reflexible regular maps.

Suppose G is any group generated by three involutions a, b and c such that ac has order 2, and ab and bc have orders greater than 2, say p and q respectively. Then the vertices, edges and faces of a map M = M(a, b, c) may be taken as the right cosets in G of the subgroups V = ⟨b, c⟩, E = ⟨a, c⟩ and F = ⟨a, b⟩ respectively, and incidence defined by non-empty intersection of these cosets. Then the group G = ⟨a, b, c⟩ acts as a group of automorphisms of M, and transitively (and hence regularly) on its blades. Unless degenerate, this map M is regular of type {p, q}. Also M is orientable if the subgroup ⟨ab, bc⟩ of G has index 2 in G, and nonorientable if this index is 1.

Now using this correspondence between regular maps and generators for their automorphism groups, one can set about finding regular maps on surfaces of up to given genus by determining groups with the appropriate properties — or more specifically, non-degenerate finite homomorphic images of the extended (2, p, q) triangle groups ⟨ A, B, C | A^{2} = B^{2} = C^{2} = (AB)^{2} = (BC)^{p} = (CA)^{q} = 1 ⟩. As an illustration, we have the following well-known construction for regular maps on orientable surfaces of every possible genus:

Example 4.1 For any positive integer m, let G be the dihedral group of order 8m, generated by elements u and v such that u^{2} = v^{4m} = (uv)^{2} = 1. Taking involutions a = u, b = uv, and c = uv^{2m}, we have pairwise products ab = v and bc = v^{2m−1} of order 4m, and ca = v^{2m} of order 2. The corresponding regular map M = M(a, b, c) is orientable since ⟨ab, bc⟩ = ⟨v⟩ has index 2 in G. Its Euler characteristic is χ = |D_{4m}|(1/8m − 1/4 + 1/8m) = 2 − 2m. Thus for every m ≥ 1 there exists a regular map of type {4m, 4m} on an orientable surface of genus m.

Also regular maps of type {3, 7} (with the maximum possible number of symmetries for given genus) can be constructed from non-degenerate quotients of the extended (2, 3, 7) triangle group.

In fact there are infinitely many orientable regular maps of type {3, 7}, and also infinitely many non-orientable regular maps of type {3, 7}. Macbeath’s 1969 theorem [45] provides infinitely many orientable examples with Aut M ≅ PGL_{2}(q) or PSL_{2}(q) × C_{2} for various q, and infinitely many non-orientable examples with Aut M ≅ PSL_{2}(q) for some q, depending on the choice of an involution which inverts the Hurwitz generators of PSL_{2}(q) in each case. Similarly the author’s 1980 theorem [9] provides orientable examples with Aut M ≅ S_{n} or A_{n} × C_{2} for all n ≥ 168, and also non-orientable examples with Aut M ≅ A_{n} for all n ≥ 168, as both A_{n} and S_{n} are obtainable as homomorphic images of the extended (2, 3, 7) triangle group in such a way that the ordinary (2, 3, 7) triangle group maps onto A_{n}, for all n ≥ 168, and many smaller n besides.

In addition, we note here that Macbeath and Singerman developed ways of constructing infinite families of examples of covering maps of a given example of a regular map of type {3, 7}; see [52] for details.

A related method works as follows, to produce an infinite family of semi-direct products of cyclic groups by a given rotation group under certain circumstances:

Construction 4.1 Suppose H is any finite group which can be generated by two elements x and y of orders 2 and p respectively, where p is even, such that y ∉ ⟨xy, y^{2}⟩. Also let K be a cyclic group of arbitrary order n, generated say by z. Now form the semi-direct product KH of K by H, with H acting on K so that x and y both invert z, and let G be the subgroup generated by X = zx and Y = y. Because xzx = z^{−1}, we see that X has order 2, and clearly Y has order p. Further, if xy has order q then (XY)^{q} = (zxy)^{q} = z^{q}(xy)^{q} = z^{q}, so XY has order qm, where m = n/ gcd(n, q), the order of z^{q}. Thus G is a (2, p, qm)-generated group, having the original (2, p, q)-generated group H as a quotient. For increasing n, we obtain a family of such groups, with orders in arithmetic progression.

This construction (given in [16]) has numerous applications. For example, taking H as the dihedral group D_{4} = ⟨ x, y | x^{2} = y^{4} = (xy)^{2} = 1 ⟩ gives a family of rotation groups of order 8n acting on orientable rotary maps of type {4, 2n} and genus n − 1, for every n > 1; these are known as Accola-Maclachlan groups, and will be referred to again in Section 4.6.

4.4 Non-orientable regular maps

Under similar conditions, the construction described above can be taken further, to provide a means of taking a regular map M whose automorphism group is a quotient H of the extended (2, p, q) triangle group, for even p, and producing from this an infinite family of regular maps of type {p, qm} for increasing m, each being an m-fold cover of the base map M of type {p, q} associated with H.

For example, if H is the octahedral group S_{4}, which is a quotient of the extended (2, 3, 4) triangle group ⟨ A, B, C | A^{2} = B^{2} = C^{2} = (AB)^{2} = (BC)^{3} = (CA)^{4} = 1 ⟩ via a homomorphism which takes A to (1,2)(3,4), B to (3,4) and C to (2,3), this construction gives a family of groups of order 24m which are the automorphism groups of non-orientable regular maps of type {4, 3m} and genus 3m − 2, for every m > 1. In particular, this shows that regular maps exist on non-orientable surfaces of every genus g ≡ 1 mod 3.

Further details are given in [19], where it is shown how the same method of construction (with variable choice of H) can be used to prove that there exist finite regular maps on non-orientable surfaces of over 77.5% of all possible genera.

The complete genus spectrum of non-orientable regular maps is not known. Apart from genus 2 and 3 (which are somewhat trivial exceptions), it is known that no such maps exist on non-orientable surfaces of genus 18, 24, 27, 39 or 48 (by unpublished work of Antonio Breda and Steve Wilson). Also recently Wilson and the author have shown there is no such map of genus 87.

This may be contrasted with orientable regular maps, which are known to exist for all possible genera (see Example 4.1, although it should be noted here that the underlying graphs of maps in this family have multiple edges). We will return to this matter later.

4.5 Regular maps of small genus

A slightly different way of looking at the automorphism groups of reflexible regular maps is to consider them as non-degenerate finite images of the extended (2, ∞, ∞) triangle group Φ = ⟨ A, B, C | A^{2} = B^{2} = C^{2} = (AB)^{2} = 1 ⟩, under a homomorphism θ taking A to c, B to a, and C to b. By Theorem 4.1, the automorphism group of any such map M is a homomorphic image of Φ of order at most 168(g −1) if M is orientable of genus g > 1, or 84(g −2) if M is non-orientable of genus g > 2.

If G = ⟨a, b, c⟩ is any such image, then of course we take p and q to be the orders of the images ab and bc (of BC and CA) in order to obtain the type (and hence also the genus) of the map, and we still consider the index of the image ⟨ab, bc⟩ of the subgroup ⟨BC, CA⟩ in order to determine orientability.

Note that if the latter index is 1, then each of a, b and c is expressible as a word in ab and bc, or equivalently, these three involutory generators of G satisfy some relation in which the total number of occurrences of a, b and c is odd, and hence the kernel of the homomorphism θ: Φ → G contains some word in the generators A, B, C of Φ of odd length. Conversely, if ker θ contains such an odd-length word, then the corresponding word in the generators of G will be trivial and so one (and hence all) of a, b, c will lie in the subgroup ⟨ab, bc⟩.

These observations have been used together with a search for normal subgroups of low index in the group Φ (and related groups) in the determination of all orientable regular maps of genus 2 to 15 inclusive, and all non-orientable regular maps of genus 3 to 30 inclusive, with the help of Peter Dobcsanyi’s Kaláka system (as described in Section 2.3).

In fact rather than search for all normal subgroups of index up to 168×14 = 2352 in the extended (2, ∞, ∞) triangle group Φ, the search was broken down into four sub-searches, for normal subgroups of index up to 2352 in the extended (2, 3, 7) triangle group, index up to 1344 in the extended (2, 3, ∞) triangle group, index up to 1120 in the extended (2, 4, ∞) triangle group, and index up to 560 in Φ itself.

The same approach works for chiral maps — which are orientable and have the maximum possible number of rotational symmetries but no reflective symmetries — by considering homomorphic images of the ordinary (2, ∞, ∞) triangle group ⟨x, y, z | x^{2} = xyz = 1 ⟩ which take y and z to the rotational symmetries R and S described in Section 4.1.

Here one needs a way of determining chirality (or irreflexibility), which is equivalent to the non-existence of an involutory automorphism of the rotation group G^{+} = ⟨R, S⟩ inverting each of R and S (as in mirror reflection). This however is quite strightforward to check, by replacing all occurrences of R and S in the defining relations for G^{+} by their inverses, and checking whether or not the resulting words remain as relations. If all the new words are relations, then the map is reflexible and so can be eliminated, while on the other hand if some relation becomes a non-relation under this substitution, then no reflection exists and so the map is chiral. Such a test can easily be built into a post-processing phase of the normal subgroups adaptation of the low index subgroups process, if desired.

The details and results for all three types of regular map of small genus may be found in [25].

4.6 Group actions on non-orientable surfaces

Hurwitz’s theorem gives an upper bound of 84(g − 1) on the number of conformal automorphisms of a compact orientable surface X of given genus g > 1. This maximum is achieved for infinitely many but relatively few genera.

It is also interesting to ask for a lower bound on the maximum number of conformal automorphisms of a compact orientable surface of given genus. The answer to this question was obtained independently by Accola [1] and Maclachlan [46], who proved that if μ(g) denotes the largest number of conformal automorphisms of a compact Riemann surface of genus g, then μ(g) ≥ 8g + 8 for all g > 1, and this lower bound on μ(g) is sharp for infinitely many g.

For non-orientable surfaces, David Singerman [52] proved the following analogue of Hurwitz’s theorem in 1969:

Theorem 4.2 If X is a compact non-orientable surface of genus p > 2, then |Aut X| ≤ 84(p − 2), and moreover, the upper bound on this order is attained if and only if there exists a homomorphism from the extended (2, 3, 7) triangle group onto Aut X which maps the ordinary (2, 3, 7) triangle group also onto Aut X.

It is also natural to ask for an analogue of the Accola-Maclachlan theorem: what is a lower bound on the maximum number of automorphisms of a compact nonorientable surface X of given genus p > 2?

A partial answer has been provided by the author in joint work with Colin Maclachlan and Steve Wilson: if the maximum number is ν(p), then ν(p) ≥ 4p if p is odd, while ν(p) ≥ 8(p − 2) if p is even. Further refinements are also possible for genus p in specific residue classes mod 12. Indeed:

ν(p) ≥ \{ \begin{matrix}8(p + 2) & if p ≡ 1 mod 3 \\ 8(p − 2) & if p ≡ 2 mod 3 or p ≡ 0 mod 6 \\ 6(p + 1) & if p ≡ 9 mod 12 \\ 4p & if p ≡ 3 mod 12. \end{matrix}

This work has not yet been published, but has been the subject of a recent PhD thesis [53] by Sanja Todorovic-Vasiljevic, who has proved that each of these bounds is sharp for infinitely p in the corresponding residue class mod 12, with the possible (but unlikely) exception of the last case, of genus p ≡ 3 mod 12.

To explain this further, some more background material is needed.

If X is a compact non-orientable surface of genus p > 2, then X ≅ U/Λ, where U is the upper-half complex plane, and Λ is a subgroup of PGL_{2}(IR) containing both conformal and anti-conformal homeomorphisms of U, and acting on U without fixed points. Also Aut X ≅ Γ/Λ where Γ is a discrete subgroup of PGL_{2}(IR), equal to the normaliser of Λ in PGL_{2}(IR), and known as a non-Euclidean crystallographic group (or NEC group). Every NEC group is either Fuchsian (contained in PSL_{2}(IR)) or proper (not contained in PSL_{2}(IR)). As Λ contains anticonformal homeomorphisms of U, both Λ and Γ are proper NEC groups, and the natural homomorphism from Γ to Γ/Λ ≅ Aut X maps the index 2 subgroup Γ^{+} = Γ ∩ PSL_{2}(IR) onto G = Aut X.

Conversely, if Γ is any proper NEC group, and θ is a homomorphism from Γ to any finite group G such that the kernel of θ is a non-orientable surface group and θ maps Γ^{+} = Γ ∩ PSL_{2}(IR) onto G, then the orbit space X = U/ ker θ is a nonorientable surface on which the group G acts faithfully as a group of automorphisms.

The genus of the surface X depends on the signature of Γ, corresponding to the analytic structure which is determined largely by fixed circles of reflections in Γ and branch points of Γ^{+}, of the form (γ; ±; [m_{1}, …, m_{τ}]; {(n_{i1}, …, n_{is_{i}}) : 1 ≤ i ≤ k}). Each signature determines a defining presentation for the NEC group Γ in terms of certain elements, the orders of some of which must be preserved by the homomorphism θ : Γ → G. That being the case, the genus p and the Euler characteristic χ of the associated surface X are given by the Riemann-Hurwitz equation 2 − p = χ = |G|ξ, where in the + case

ξ = 2 − 2γ − k − ∑_{i=1}^{τ} (1 − 1/m_{i}) − ∑_{i=1}^{k} ∑_{j=1}^{s_{i}} (1 − 1/n_{ij})/2 ,

while in the − case, 2 − 2γ − k is replaced by 2 − γ − k.

For example, if p is any odd integer > 2 then there is a homomorphism from the NEC group with signature (0; +; [−]; {(2, 2, 2, p)}) to the dihedral group D_{2p} of order 4p, preserving the orders of appropriate elements, and mapping the conformal subgroup onto D_{2p}. Thus D_{2p} acts faithfully on a non-orientable surface of characteristic χ = 4p(−1/4 + 1/2p) = 2 − p and genus p. This gives the lower bound ν(p) ≥ 4p for odd p, and the other bounds listed above can be obtained in a similar fashion.

Also if p ≡ 3 mod 6 and p − 2 is prime, then there exists a homomorphism from the NEC group with signature (0; +; [2, 3]; {(1)}) onto the semi-direct product C_{p−2} ·C_{6} having the required properties, and hence there exits a compact nonorientable surface of genus p with an automorphism group of order 6(p−2). When p ≡ 3 mod 6 and p − 2 = m^{2}, a perfect square, a similar homomorphism onto (C_{m}×C_{m})·C_{6} provides another such group of order 6(p−2), and so ν(p) ≥ 6(p−2) whenever p − 2 is a product of integer squares and primes congruent to 1 mod 6. This, however, still leaves infinitely many p congruent to 3 modulo 12 for which the bound ν(p) ≥ 4p appears to be the best possible.

To prove sharpness of this (or other bounds listed above), we may assume the bound on ν(p) is exceeded, which in turn gives a lower bound on the Euler characteristic χ in terms of the order of the group G = Aut X. This severely restricts the possibilities for the signature of the NEC group Γ associated with X.

For example assuming |G| > 4p gives χ > −|G|/4, which restricts the signature to one of the following:

(a) (1; −; [2, 3]; {})

(b) (0; +; [2, 3]; {(1)})

(c) (0; +; [2]; {(n_{1}, n_{2})}) where 1/2 + 1/p < 1/n_{1} + 1/n_{2} < 1

(d) (0; +; [3]; {(2, 2)})

(e) (0; +; [m]; {(n)}) where 1/4 + 1/p < 1/m + 1/2n < 1/2

(f) (0; +; [−]; {(2, n_{1}, n_{2})}) where 1/p < 1/n_{1} + 1/n_{2} < 1/2

(g) (0; +; [−]; {(3, n_{1}, n_{2})}) where 1/6 + 1/p < 1/n_{1} + 1/n_{2} < 2/3

(h) (0; +; [−]; {(4, n_{1}, n_{2})}) where 1/4 + 1/p < 1/n_{1} + 1/n_{2} < 3/4

(i) (0; +; [−]; {(5, n_{1}, n_{2})}) where 3/10 + 1/p < 1/n_{1} + 1/n_{2} < 4/5

(j) (0; +; [−]; {(2, 2, 2, n)}) where 3 ≤ n < p

(k) (0; +; [−]; {(2, 2, 3, n)}) where 3 ≤ n ≤ 5.

Many of these cases can be eliminated in a number of different ways for infinitely many p of the form Mq + 2 where M and q are primes, each congruent to 11 mod 12, with M fixed (and small) and q large and variable, and satisfying certain other conditions such as q ≢ 1 mod M.

Frequently the Riemann-Hurwitz equation gives |G| = μ(p−2) = μMq where μ is a rational number whose denominator fails to divide Mq, or gives |G| as an integer which fails to be divisible by the orders (periods) of the generators prescribed by the corresponding signature. Also if |G| = 6(p − 2) = 6Mq then by choice of M and q and Sylow theory the group G has a cyclic normal subgroup of order 3Mq = 3(p − 2), which is contrary to Bujalance’s 1983 theorem on maximal cyclic group actions [7]; thus |G| ≠ 6(p − 2), eliminating signature types (a), (b) and (d).

In some cases more advanced methods are required. For example, often Sylow theory shows G has a cyclic normal subgroup K of order q, with C_{G}(K) of low index, and then by the Schur-Zassenhaus theorem C_{G}(K) has a quotient of order q, while the Reidemeister-Schreier process shows that all subgroups of low index are generated by elements of order coprime to q, making this impossible. Similarly a theorem of Schur on the transfer (to the effect that the exponent of the commutator subgroup G′ divides the index |G: Z(G)| of the centre of a group G) may be used to limit q to finitely many possibilities, for certain signatures.

The main difficulty lies with case (f), involving signature (0; +; [−]; {(2, m, n)}) for large m and n. Here the corresponding NEC group presentation is nothing other than ⟨ A, B, C | A^{2} = B^{2} = C^{2} = (AB)^{2} = (BC)^{m} = (CA)^{n} = 1 ⟩, which is the extended (2, m, n) triangle group, associated with regular maps of type {m, n}.

Hence proving sharpness of the bound ν(p) ≥ 4p for p ≡ 3 mod 12 is intimately associated with the question of non-existence of regular maps on non-orientable surfaces of infinitely many genera congruent to 3 mod 12. See [28, 53] for further details.

5 Symmetric graphs

5.1 Definitions and background

Let X = (V, E) be an undirected simple graph. A symmetry (or automorphism) of X is a permutation of its vertices preserving adjacency, that is, a bijection π : V → V with the property that {π(x), π(y)} ∈ E whenever {x, y} ∈ E. Under composition, the symmetries of a graph X form a group called the automorphism group of X, and denoted by Aut X.

Finite graphs with maximum symmetry are very easy to classify: the largest possible number of automorphisms of a graph on n vertices is n!, and this is achieved only by the null graph N_{n} (which has no edges) and its complement the complete graph K_{n} (in which every two vertices are joined by an edge). These examples, however, are rather uninteresting, and graphs of more frequent attention are those which lie in between these two extremes but have an automorphism group which acts transitively on vertices, edges, arcs, or directed walks of a given length.

If Aut X has a single orbit on vertices, then the graph X is said to be vertextransitive. Similarly if Aut X is transitive on the edges of X, or on arcs (directed edges) of X, then X is edge-transitive or arc-transitive respectively.

Taking this further, an s-arc in a graph X is defined as an ordered (s + 1)- tuple (v_{0}, v_{1}, …, v_{s}) of vertices of X such that any two consecutive v_{i} are adjacent in X and any three consecutive v_{i} are distinct, that is, {v_{i−1}, v_{i}} ∈ E(X) for 1 ≤ i ≤ s and v_{i−1} ≠ v_{i+1} for 1 ≤ i < s. If Aut X has just a single orbit on s-arcs then X is said to be s-arc-transitive. Thus 0-arc-transitivity is the same as vertex-transitivity, and 1-arc-transitivity the same as arc-transitivity. Connected 1-arc-transitive graphs are also called symmetric. Note that symmetric graphs are necessarily vertex-transitive, and therefore regular (in the sense that every vertex has the same degree, or valency). Also note that under the assumption of connectedness, s-arc-transitivity implies (s − 1)-arc-transitivity, for all s ≥ 1.

Examples 5.1

• The complete graph K_{n} is vertex-, edge- and arc-transitive, for all n ≥ 3, but is 2-arc-transitive only when n = 3 (as there are two types of 2-arc when n ≥ 4);

• the simple cycle C_{n} is s-arc-transitive for all s ≥ 0; • the 1-skeleton of a cube is 2-arc- but not 3-arc-transitive;

• the complete bipartite graph K_{n,n} is 3-arc- but not 4-arc-transitive;

• the Petersen graph is 3-arc- but not 4-arc-transitive;

• the Heawood graph (the incidence graph of the Fano plane) is 4-arc- but not 5-arc-transitive;

• Tutte’s 8-cage (pictured in Figure 4) is 5-arc- but not 6-arc-transitive.

Figure 4. Tutte’s 8-cage

The degree of symmetry of a non-null arc-transitive graph X can be measured by the stabilizer H = G_{v} = {g ∈ G : v^{g} = v} of a vertex v in its automorphism group G = Aut X. Vertices of X can be labelled with cosets of H, and if w is any neighbour of v then there exists an automorphism a ∈ G reversing the edge {v, w}, from which it follows that the vertex v (labelled H) is adjacent to all vertices of the form w^{h} = v^{ah} (labelled Hah) for h ∈ H, as illustrated in Figure 5.

PSfrag replacements

H Ha Hah Hah′

Figure 5. Local action (on neighbourhood of H)

The vertex labelled Hx is adjacent to the vertex labelled Hy if and only if xy^{−1} lies in the double coset HaH, and from this it follows that X is connected if and only if HaH generates G. Note also that a^{2} ∈ G_{v} = H.

As with regular maps, this background theory can be exploited to produce a group-theoretic method of construction of examples of symmetric graphs. Given any group G containing a subgroup H and an element a such that a^{2} ∈ H, we may construct a graph Γ = Γ(G, H, a) on which G acts as an arc-transitive group of automorphisms, as follows: take as vertices of Γ the right cosets of H in G, and join two cosets Hx and Hy by an edge in Γ whenever xy^{−1} ∈ HaH. Defined in this way, Γ is an undirected graph on which the group G acts as a group of automorphisms under the action g : Hx → Hxg for each g ∈ G and each coset Hx in G. The stabilizer in G of the vertex H is the subgroup H itself, and as this acts transitively on the set of neighbours of H (which are all of the form Hah for h ∈ H), it follows that Γ is symmetric. Furthermore, the degree of any vertex of Γ is equal to |H : H ∩ a^{−1}Ha|, the number of right cosets of H in HaH, and the graph Γ is connected if and only if the elements of HaH generate G.

Also the background theory can be taken much further, to produce some very strong conditions on maximum symmetry.

For symmetric graphs of valency 3 (often called trivalent, or cubic), if the automorphism group acts transitively on s-arcs then the order of the vertex-stabiliser must be divisible by 3 × 2^{s−1}. In 1947 Tutte proved the following remarkable theorem by local analysis:

Theorem 5.1 (Tutte [54, 55]) If X is a finite trivalent graph with arc-transitive automorphism group G, then G acts regularly on the s-arcs of X for some s ≤ 5, and in particular, |G_{v}| ≤ 48 for all v ∈ V (X).

This may be contrasted starkly with the 4-valent case, where generalisations of the graph in Figure 6 show that the stabiliser of a vertex can be arbitrarily large.

Figure 6. An arc-transitive 4-valent graph with large vertex-stabiliser

Nevertheless there is still an upper limit on s-arc-transitivity for finite 4-valent graphs, and indeed for finite symmetric graphs of valency greater than 2 in general. If X is 2-arc-transitive, then the stabiliser of a vertex v is doubly-transitive on the neighbourhood X(v) of v. Using this observation and the classification of doublytransitive finite permutation groups (based in turn on the classification of finite simple groups), Richard Weiss proved the following spectacular generalisation of Tutte’s theorem in 1981:

Theorem 5.2 (Weiss [56]) If X is a finite s-arc-transitive graph of degree d > 2, then s ≤ 7, and moreover, if s = 7 then d = 3^{m} + 1 for some positive integer m.

In particular, there are no finite 8-arc-transitive graphs of valency greater than 2.

5.2 The trivalent case

By the work of Tutte, Goldschmidt, Sims, Djoković and others, the automorphism group of every arc-transitive finite trivalent graph is a factor group of one of seven finitely-presented groups which can be listed as G_{1}, G_{2}^{1}, G_{2}^{2}, G_{3}, G_{4}^{1}, G_{4}^{2} and G_{5}. Here the group G_{s} or G_{s}^{i} corresponds to a regular action of the automorphism group on s-arcs, with i = 0 or 1 depending on whether or not the arc-reversing automorphism a described in Section 5.1 can be taken as an involution (see [33]). Presentations for these seven groups may be taken as follows (see [13]):

G_{1} = ⟨ h, a | h^{3} = a^{2} = 1 ⟩ (the modular group)

G_{2}^{1} = ⟨ h, p, a | h^{3} = p^{2} = a^{2} = 1, php = h^{−1}, a^{−1}pa = p ⟩

G_{2}^{2} = ⟨ h, p, a | h^{3} = p^{2} = 1, a^{2} = p, php = h^{−1}, a^{−1}pa = p ⟩

G_{3} = ⟨ h, p, q, a | h^{3} = p^{2} = q^{2} = a^{2} = 1, pq = qp, php = h, qhq = h^{−1}, a^{−1}pa = q ⟩

G_{4}^{1} = ⟨ h, p, q, r, a | h^{3} = p^{2} = q^{2} = r^{2} = a^{2} = 1, pq = qp, pr = rp, (qr)^{2} = p, h^{−1}ph = q, h^{−1}qh = pq, rhr = h^{−1}, a^{−1}pa = p, a^{−1}qa = r ⟩

G_{4}^{2} = ⟨ h, p, q, r, a | h^{3} = p^{2} = q^{2} = r^{2} = 1, a^{2} = p, pq = qp, pr = rp, (qr)^{2} = p, h^{−1}ph = q, h^{−1}qh = pq, rhr = h^{−1}, a^{−1}pa = p, a^{−1}qa = r ⟩

G_{5} = ⟨ h, p, q, r, s, a | h^{3} = p^{2} = q^{2} = r^{2} = s^{2} = a^{2} = 1, pq = qp, pr = rp, ps = sp, qr = rq, qs = sq, (rs)^{2} = pq, h^{−1}ph = p, h^{−1}qh = r,

h^{−1}rh = pqr, shs = h^{−1}, a^{−1}pa = q, a^{−1}ra = s ⟩.

Conversely, every non-degenerate homomorphic image of one of these seven groups acts arc-transitively on a connected trivalent graph whose vertices may be identified with cosets of a certain subgroup, namely ⟨h⟩ in the case of G_{1}, or ⟨h, p⟩ in the case of G_{2}^{1} and G_{2}^{2}, or ⟨h, p, q⟩ in the case of G_{3}, or ⟨h, p, q, r⟩ in the case of G_{4}^{1} and G_{4}^{2}, or ⟨h, p, q, r, s⟩ in the case of G_{5}.

These observations were exploited in [13] to produce the first known examples of finite trivalent symmetric graphs of the types corresponding to G_{2}^{2} and G_{4}^{2} (having no involutory automorphism flipping an edge).

More recently, using the normal subgroups adaptation of the low index subgroups algorithm described in Section 2.3, Peter Dobcsányi and the author have determined all finite trivalent symmetric graphs on up to 768 vertices (see [26]). In particular, this extends the Foster census [6] of such graphs of order up to 512 (compiled largely by hand by by R.M. Foster), confirming the census for graphs of order up to 402 (with just one omission corrected in its publication), and filling some of the gaps from 408 to 512. Also as a bonus discovery, one of the graphs found in [26] but not in [6], on 448 vertices and of type G_{2}^{2}, is the smallest finite arc-transitive trivalent graph having no arc-reversing automorphism of order 2.

Examples of finite 5-arc-transitive trivalent graphs include Tutte’s 8-cage (on 30 vertices) and Wong’s graph (on 234 vertices), which are described in [3] along with a method (due to John Conway) for constructing an infinite number of covers of any given example. Further examples include many of the sextet graphs constructed by Biggs and Hoare in [4], using projective linear groups PGL_{2}(p) and PΓL_{2}(p^{2}) for certain primes p.

For some time these examples (and their covers) and other bipartite examples were the only finite 5-arc-transitive trivalent graphs known, until the author of this paper adapted the construction of Tutte’s 8-cage to produce an example on 75600 vertices with S_{10} as its automorphism group, and then used techniques of coset graph composition to prove that for all but finitely many positive integers n, examples may be constructed with the alternating group A_{n} and the symmetric group S_{n} as automorphism groups (see [12]).

The key to the latter construction comes from the fact that the automorphism group of any finite 5-arc-transitive trivalent graph is a homomorphic image of the group G_{5} given above, with the stabiliser of a vertex being the image of the subgroup H = ⟨ h, p, q, r, s ⟩, of order 3 × 2^{4} = 48, and with the image of the element a reversing an edge. The subgroup A = ⟨ p, q, r, s ⟩ is normalised by the involution a, has index 3 in H, and its image is the stabiliser of an arc. It can now be observed that in any transitive permutation representation of G_{5}, all orbits of H have lengths dividing 48, and decompose into orbits of A which are linked together by cycles of the permutations induced by h and a.

This observation makes it easy to construct multitudes of transitive permutation representations of G_{5} of arbitrarily large degree, in a similar way to representations of the (2, 3, 7) triangle group, and hence multitudes of 5-arc-transitive cubic graphs.

5.3 Finite 7-arc-transitive graphs

Weiss’s theorem [56] shows that finite symmetric graphs of valency greater than 2 are at most 7-arc-transitive, and that 7-arc-transitivity can occur only in cases where the valency is of the form 3^{m}+ 1 for integer m.

Examples exist with the maximum possible symmetry — indeed the incidence graph of the generalised hexagon associated with the simple group G_{2}(3^{m}) is a 7-arc-transitive graph of valency 3^{m}+ 1, for all m ≥ 1. The smallest such example is the one associated with G_{2}(3), on 728 vertices, and larger examples can be constructed as covers of given examples under certain conditions (see [30, 57]).

Further, as in the case of finite 5-arc-transitive cubic graphs, for each k of the form 3^{m}+ 1 there exists a generic infinite but finitely-presented group R_{k,7}, with generators prescribed in terms of specific types of symmetries, such that if X is any finite 7-arc-transitive graph of valency k, then its automorphism group Aut X must be a homomorphic image of R_{k,7} (see [57]). Also conversely, every non-degenerate homomorphic image of R_{k,7} acts 7-arc-transitively on a connected k-valent graph whose vertices may be identified with cosets of a certain subgroup.

In response to a challenge by Norman Biggs, the author used this information to prove the following, in joint work with Cameron Walker [21]:

Theorem 5.3 For all but finitely many positive integers n, both the alternating group A_{n} and the symmetric group S_{n} may be represented as 7-arc-transitive groups of automorphisms of finite connected 4-valent graphs.

The proof is based on a careful selection of permutation representations of the generic group R_{4,7} as building blocks for constructing transitive permutation representations of arbitrarily large degree, as in [12].

The group R_{4,7} itself may be taken to have generators p, q, r, s, t, u, v, h and b, subject to the following defining relations:

h^{4} = p^{3} = q^{3} = r^{3} = s^{3} = t^{3} = u^{3} = v^{2} = b^{2} = 1,

(hu)^{3} = (uv)^{2} = (huv)^{2} = [h^{2}, u] = [h^{2}, v] = 1,

[p, q] = [p, r] = [p, s] = [p, t] = [q, r] = [q, s] = [q, t] = [r, s] = [r, t] = 1,

[s, t] = p, h^{−1}ph = p, h^{−1}qh = q^{−1}r, h^{−1}rh = qr, h^{−1}sh = pq^{−1}r^{−1}s^{−1}t^{−1},

h^{−1}th = p^{−1}qr^{−1}s^{−1}t, u^{−1}pu = p, u^{−1}qu = q, u^{−1}ru = q^{−1}r, u^{−1}su = s, u^{−1}tu = pqrst, vpv = p^{−1}, vqv = q^{−1}, vrv = r, vsv = s, vtv = t^{−1}, bpb = q^{−1}, bqb = p^{−1}, brb = s^{−1}, bsb = r^{−1}, btb = u^{−1}, bub = t^{−1}, bvb = v, and bh^{2}b = h^{2}v.

The role of vertex-stabiliser is played by the subgroup H = ⟨ h, p, q, r, s, t, u, v ⟩, which is a semi-direct product of the normal subgroup M = ⟨ p, q, r, s, t ⟩ of order 3^{5} by the complementary subgroup L = ⟨ h, u, v ⟩ ≅ GL_{2}(3) of order 48. In particular, H has order 11664. The generator b takes the role of the arc-reversing involution a in the construction described in Section 5.1, and this normalises the index 4 subgroup K = ⟨ h^{2}, p, q, r, s, t, u, v ⟩, indeed K = H ∩ b^{−1}Hb. In any permutation representation of R_{4,7}, orbits of the subgroup H can be decomposed into orbits of the subgroup K = H ∩ b^{−1}Hb, which are linked together by 2-cycles of the permutation induced by b, and 2- and 4-cycles of the permutation induced by h.

For our construction in [21], we chose as building blocks two transitive permutation representations A and B of R_{4,7} on 2912 and 8825 points respectively, each having two points fixed by both K and b. Each block in turn was made up of representations of smaller degree, linked together by multiple transpositions of b.

Now any sufficiently large n can be written in the form 2912k + 8825l where k and l are positive integers, since 2912 and 8825 are relatively prime. Taking k copies of the block A and l copies of B, we may link these together into a chain to produce a transitive permutation representation of R_{4,7} on n points.

If the order in which the blocks are linked is chosen carefully, then the permutation induced by bh will have a single cycle of length 107, and lengths of all other cycles will be relatively prime to 107. With the help of Jordan’s theorem, this is enough to show the permutations generate S_{n}.

Similarly by linking a copy of the trivial permutation representation of the subgroup H to one end of the chain, we may obtain A_{n+1} as a non-degenerate factor group of R_{4,7} as well, proving the theorem.

6 Some unexpected results/surprises

In this Section we briefly describe two instances of unexpected results of research on graphs with large symmetry groups.

The first arose in answer to a question posed by Norman Biggs in his continuation of work begun by John Conway, on the result of inserting an extra relator into a generic partial presentation for a group of automorphisms of a 4- or 5-arc-transitive 3-valent graph (corresponding to the presence of a circuit of specific type).

Somewhat surprisingly, it turns out that adjoining the extra relation (ha)^{12} = 1 to the presentation

⟨ h, p, q, r, a | h^{3} = p^{2} = q^{2} = r^{2} = a^{2} = 1, pq = qp, pr = rp, (qr)^{2} = p,
h^{−1}ph = q, h^{−1}qh = pq, rhr = h^{−1}, a^{−1}pa = p, a^{−1}qa = r ⟩

given for the group G_{4}^{1} in Section 5 produces a group which is isomorphic to the semi-direct product SL_{3}(ZZ) : ⟨θ⟩, where θ is the inverse-transpose automorphism; see [14] and [30]. In particular, this produces an unexpectedly succinct presentation for the group SL_{3}(ZZ). In a personal communication, Peter Neumann has given a partial explanation for the isomorphism, associated with a 3-valent graph of incidence between quadrangles and quadrilaterals in a finite projective plane.

The second arose in the construction of a family {X_{n}} of arc-transitive 4-valent graphs in which the orders of vertex-stabilisers in vertex-transitive subgroups of Aut X_{n} of smallest possible order form a strictly increasing sequence [22]. Here Sierpinski’s gasket (Pascal’s triangle modulo 2) plays an important role, and recognition of the underlying pattern has led to a direct (closed form) definition [23] of the binary reflected Gray codes, simply in terms of binomial coefficients modulo 2.

7 Some open problems

We conclude with a number of open problems in this area of research:

Problem 1: Complete the determination of those finite simple groups which are Hurwitz. (Note: only groups of Lie type remain to be considered.)

Problem 2: What is the complete genus spectrum of non-orientable regular maps?

Problem 3: Is it true that for every positive integer g there exists a regular map on an orientable surface of genus g such that the underlying graph is simple? (Note: the underlying graphs of the families of examples customarily used to show orientable maps exist for all possible genera have multiple edges.)

Problem 4: Prove sharpness of the lower bound of 4p on the maximum number of automorphisms of a non-orientable surface of given genus p, for infinitely many p ≡ 3 modulo 12. (Note: this will involve proving there are infinitely many such p for which there is no non-orientable map of genus p.)

Problem 5: Obtain a classification of all finite 2-arc-transitive graphs. (Note: considerable progress has been made on this by Cheryl Praeger.)

Problem 6 (proof of the Weiss conjecture): Prove that the order of the vertexstabiliser in any vertex-transitive and locally primitive group of automorphisms of a finite, connected, non-bipartite graph is bounded by a function of the valency. More specifically, prove there exists an integer-valued function f such that if G is any group of automorphisms of a finite, connected, non-bipartite graph X such that G is transitive on the vertices of X and the stabilizer in G of a vertex v is primitive on the neighbourhood X(v) of v, then |G_{v}| < f(d) where d = |X(v)|. (Note: Cheryl Praeger and Cai Heng Li and have reduced this problem to the case where the socle soc(G) is simple and vertex-transitive on X; see [24].)

Acknowledgement

The author is grateful to the organisers of the Groups St Andrews conference for the invitation to speak at the Oxford conference, and to the N.Z. Marsden Fund for its financial support.

Electronic Availability

An implementation of the normal subgroups adaptation of the low index subgroups process is available (together with tables of results obtained from it) at

http://www.scitec.auckland.ac.nz/∼peter.

References

[1] R.D.M. Accola, On the number of automorphisms of a closed Riemann surface, Trans. Amer. Math. Soc. 131 (1968), 398–408.

[2] H.R. Brahana, Regular maps and their groups, Amer. J. Math. 49 (1927), 268–284.

[3] N.L. Biggs, Algebraic Graph Theory, Cambridge Univ. Press (London, 1974).

[4] N.L. Biggs and M.J. Hoare, The sextet construction for cubic graphs, Combinatorica 3 (1983), 153–165.

[5] W. Bosma, J. Cannon & C. Playoust, The Magma Algebra System I: the user language, J. Symbolic Comput. (24) (1997), 235–265.

[6] I.Z. Bouwer (ed.), The Foster Census, Charles Babbage Research Centre (Winnipeg, 1988).

[7] Emilio Bujalance, Cyclic groups of automorphisms of compact non-orientable Klein surfaces without boundary, Pacific J.Math. 109 (1983), 279–289.

[8] J. Cohen, On non-Hurwitz groups and noncongruence subgroups of the modular group, Glasgow Math. J. 22 (1981), 1–7.

[9] M.D.E. Conder, Generators for alternating & symmetric groups, J. London Math. Soc. (2) 22 (1980), 75–86.

[10] M.D.E. Conder, The genus of compact Riemann surfaces with maximal automorphism group, J. Algebra 108 (1987), 204–247.

[11] M.D.E. Conder & J. McKay, A necessary condition for transitivity of a finite permutation group, Bull. London Math. Soc. 20 (1988), 235–238.

[12] M.D.E. Conder, An infinite family of 5-transitive cubic graphs, Ars Combinatoria 25A (1988), 95–108.

[13] M.D.E. Conder & P.J. Lorimer, Automorphism groups of symmetric graphs of valency 3, J. Combinatorial Theory, Series B 47 (1989), 60–72.

[14] M.D.E. Conder, A surprising isomorphism, J.Algebra 129 (1990) 494–501.

[15] M.D.E. Conder, Hurwitz groups: a brief survey, Bull. American Math. Society 23 (1990), 359–370.

[16] M.D.E. Conder & R.S. Kulkarni, Infinite families of automorphism groups of Riemann surfaces, in: Discrete Groups and Geometry (ed. W.J. Harvey & C. Maclachlan),

L.M.S. Lecture Note Series 173 (Cambridge University Press, 1992), pp. 47–56.

[17] M.D.E. Conder, R.A. Wilson and A.J. Woldar, The symmetric genus of sporadic groups, Proc. Amer. Math. Soc. 116 (1992), 653–663.

[18] M.D.E. Conder & G.J. Martin, Cusps, triangle groups and hyperbolic 3-folds, J. Austral. Math. Soc. (Series A) 55 (1993), 149–182.

[19] M.D.E. Conder & B.J. Everitt, Regular maps on non-orientable surfaces, Geometriae Dedicata 56 (1995), 209–219.

[20] M.D.E. Conder, Asymmetric combinatorially-regular maps, J. Algebraic Combinatorics 5 (1996), 323–328.

[21] M.D.E. Conder & C.G. Walker, The infinitude of 7-arc-transitive graphs, Journal of Algebra 208 (1998), 619–629.

[22] M.D.E. Conder & C.G. Walker, Vertex-transitive graphs with arbitrarily large vertexstabilizers, J. Algebraic Combinatorics 8 (1998), 29–38.

[23] M.D.E. Conder, Explicit definition of the binary reflected Gray codes, Discrete Math. 195 (1999), 245–249.

[24] M.D.E. Conder, Cai Heng Li & C.E. Praeger, On the Weiss conjecture for finite locally primitive graphs, Proc. Edinburgh Math. Soc. (2) 43 (2000), 129–138.

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

[26] M.D.E. Conder & P. Dobcsányi, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Comput., to appear.

[27] M.D.E. Conder, Hurwitz groups with given centre, preprint.

[28] M.D.E. Conder, C. Maclachlan, S. Todorovic Vasiljevic & S.E. Wilson, Bounds for the number of automorphisms of a compact non-orientable surface, preprint.

[29] H.S.M. Coxeter & W.O.J. Moser, Generators and Relations for Discrete Groups, 4th ed. Springer-Verlag (Berlin), 1980.

[30] A. Delgado & R. Weiss, On certain coverings of generalized polygons, Bull. London Math. Soc. 21 (1989), 235–242.

[31] L. Di Martino, M.C. Tamburini & A. Zalesskii, On Hurwitz groups of low rank. Comm. Algebra 28 (2000), 5383–5404.

[32] M.J. Dinneen & P.R. Hafner, New results for the degree/diameter problem, Networks 24 (1994), 359–367.

[33] D.Z. Djoković & G.L. Miller, Regular groups of automorphisms of cubic graphs, J. Combinatorial Theory Ser. B 29 (1980), 195–230.

[34] P. Dobcsányi, Adaptations, Parallelisation and Applications of the Low-index Subgroups Algorithm, PhD thesis, University of Auckland, 1999.

[35] B.J. Everitt, Images of Hyperbolic Reflection Groups, PhD thesis, University of Auckland, 1994.

[36] B.J. Everitt, Alternating quotients of Fuchsian groups, J. Algebra 223 (2000), 457– 476.

[37] D.F. Holt & W. Plesken, A cohomological criterion for a finitely presented group to be infinite, J. London Math. Soc. (2) 45 (1992), 469–480.

[38] G.A. Jones & D. Singerman, Theory of maps on orientable surfaces, Proc. London Math. Soc. (3) 37 (1978), 273–307.

[39] G.A. Jones & D. Singerman, Complex functions: An algebraic and geometric viewpoint. Cambridge University Press (Cambridge, 1987).

[40] G.A. Jones, Ree groups and Riemann surfaces, J. Algebra 165 (1994), 41–62.

[41] G.A. Jones, Characters and surfaces: a survey, The atlas of finite groups: ten years on (Birmingham, 1995), London Math. Soc. Lecture Note Ser., vol. 249, Cambridge Univ. Press, 1998, pp. 90–118.

[42] J. Leech, Generators for certain normal subgroups of (2, 3, 7), Proc. Cambridge Philos.

Soc. 61 (1965), 321–332.

[43] A. Lucchini and M.C. Tamburini, Classical groups of large rank as Hurwitz groups, J. Algebra 219 (1999), 531–546.

[44] A. Lucchini, M.C. Tamburini and J.S. Wilson, Hurwitz groups of large rank, J. London Math. Soc. (2) 61 (2000), 81–92.

[45] A.M. Macbeath, Generators of the linear fractional groups, Number theory (Proc. Sympos. Pure Math., Vol XII, 1967), Amer. Math. Soc., 1969, pp. 14–32.

[46] C. Maclachlan, A bound for the number of automorphisms of compact Riemann surface, J. London Math. Soc. 44 (1969), 265–272.

[47] Gunter Malle, Hurwitz groups and G_{2}(q), Canad. Math. Bull. 33 (1990), 349–357.

[48] Gunter Malle, Small rank exceptional Hurwitz groups, Groups of Lie type and their geometries (Como, 1993). London Math. Soc. Lecture Note Ser., vol.207, Cambridge Univ. Press (Cambridge, 1995), pp. 173–183.

[49] C.E. Praeger, Highly arc transitive digraphs, European J. Combinatorics 10 (1989), 281–292.

[50] Chih-han Sah, Groups related to compact Riemann surfaces, Acta Math. 123 (1969), 13–42.

[51] C.C. Sims, Computation with finitely presented groups. Encyclopedia of Mathematics and its Applications, vol. 48. Cambridge University Press (Cambridge, 1994).

[52] David Singerman, Automorphisms of compact nonorientable Riemann surfaces, Glasgow Math. J. 12 (1971), 50–59.

[53] Sanja Todorovic Vasiljevic, Bounds on the Number of Automorphisms of a Compact Non-orientable Surface of Given Genus, PhD thesis, University of Auckland, 2001.

[54] W.T. Tutte, A family of cubical graphs, Proc. Camb. Phil. Soc. 43 (1947), 459–474.

[55] W.T. Tutte, On the symmetry of cubic graphs, Canad. J. Math. 11 (1959), 621–624.

[56] Richard Weiss, The non-existence of 8-transitive graphs, Combinatorica 1 (1981), 309–311.

[57] Richard Weiss, Presentations for (G, s)-transitive graphs of small valency, Math. Proc. Cambridge Philos. Soc. 101 (1987), 7–20.

[58] H. Wielandt, Finite Permutation Groups (Academic Press, 1964).

[59] R.A. Wilson, The Monster is a Hurwitz group, preprint.

[60] S.E. Wilson, Operators over regular maps, Pacific J. Math. 81 (1979), 559–568.