On symmetries of Cayley graphs and the graphs underlying regular maps

Marston Conder

Department of Mathematics

University of Auckland

Private Bag 92019 Auckland, New Zealand

               m.conder@auckland.ac.nz

Abstract

By definition, Cayley graphs are vertex-transitive, and graphs underlying regular or orientably-regular maps (on surfaces) are arc-transitive. This paper addresses questions about how large the automorphism groups of such graphs can be. In particular, it is shown how to construct 3-valent Cayley graphs that are 5-arc-transitive (in answer to a question by Cai Heng Li), and Cayley graphs of valency 3^{t} + 1 that are 7-arc-transitive, for all t > 0. The same approach can be taken in considering the graphs underlying regular or orientably-regular maps, leading to classifications of all such maps having a 1-, 4- or 5-arc-regular 3-valent underlying graph (in answer to questions by Cheryl Praeger and Sanming Zhou).

1 Introduction

This paper uses combinatorial group theory to address some questions about symmetries of discrete structures. Specifically, it gives answers to recent questions raised by Caiheng Li (in [30]) about symmetries of Cayley graphs, and questions raised by Cheryl Praeger and Sanming Zhou (in a personal communication during the preparation of their paper [34]) about the symmetries of graphs underlying regular maps.

This work was supported in part by the Marsden Fund of New Zealand via grant UOA 412 2000 Mathematics Subject Classification: 05C25, 20B25, 57M15

To explain these, we need to give some definitions and background.

First, a symmetry (or automorphism) of a combinatorial graph X with vertex-set V and edge-set E is any permutation of V preserving E. Under composition, symmetries of X form the automorphism group of X, denoted by Aut X. If Aut X is transitive on V (that is, has a single orbit on V), then X is said to be vertex-transitive. Similarly if Aut X has a single orbit on the edges of X, then X is edge-transitive. An arc in a graph X is an ordered edge, or equivalently, an incident vertex-edge pair, and if Aut X has a single orbit on the arcs of X, then X is said to be arc-transitive, or symmetric.

The last of the above can be extended. A walk (v_{0}, v_{1}, v_{2}, …, v_{s}) of length s in X in which every two successive vertices v_{i−1} and v_{i} are adjacent and every three successive vertices v_{i−1}, v_{i} and v_{i+1} are distinct is called an s-arc of X, and if Aut X has a single orbit on the s-arcs of X, then X is said to be s-arc-transitive. In the special case where Aut X is sharply-transitive (that is, induces a regular permutation group) on the set of s-arcs, the graph X is said to be s-arc-regular.

Note that every connected vertex- or arc-transitive graph is regular in the sense of all its vertices having the same valency (degree).

Circuit graphs (connected graphs in which every vertex has valency 2) are not just vertex-, edge- and arc-transitive, but also s-arc-transitive for all s. On the other hand, by a remarkable theorem of Bill Tutte [39, 40], finite cubic (3-valent) graphs are at most 5-arc-transitive; indeed every symmetric finite cubic graph is s-arc-regular for some s ≤ 5. (Note, however, that the finite cubic graphs with the largest numbers of automorphisms with respect to their order are not even vertex-transitive; see recent work by van Opstall and Veliche [41].) Tutte’s theorem was extended by Richard Weiss in [42] to show that for all k ≥ 3, every finite symmetric graph of valency k is at most 7-arc-transitive. Furthermore, Weiss proved (using the classification of doubly-transitive finite permutation groups) that if such a graph X is 7-arc-transitive, then k = 3^{t} + 1 for some t, and that there exists at least one example for each t ≥ 1, namely a generalized hexagon over the field with 3^{t} elements; see [42, 43, 44, 37].

Next, a Cayley graph is a combinatorial graph or digraph representing the action of multiplication of the elements of a given group G by elements of a generating set S for G. In the undirected case, the vertices of are the elements of G, and the edges of the graph are all the unordered pairs of the form {g, xg} for g ∈ G and x ∈ S. Usually the generating set S is assumed to be closed under taking inverses (which makes the adjacency relation symmetric), and to exclude the identity element (which ensures the graph has no loops). This graph, denoted by Cay(G, S), admits G as a group of automorphisms by right multiplication, making it vertex-transitive: if g, h ∈ G then g(g^{−1}h) = h.

This property makes Cayley graphs a rich source of examples, of use or interest in a variety of contexts. For instance, they often make good models for interconnection networks; see papers by Hafner [21], Heydemann et al [22, 23], Lakshmivarahan et al [28], and others references therein. They also have applications to the study of finitely-generated groups and permutation groups, as in the work of Trofimov [38].

Many fundamental questions about Cayley graphs concern the size of their full automorphism group.

One such question is the following: when is it that all automorphisms of Cay(G, S) are induced by automorphisms of the group G? This gives the co-called Cayley isomorphism property (or CI-property), which has been investigated by several authors including Babai and Frankl [2, 3], Alspach [1], Dobson [17], Li [29] and Muzychuk [32].

Another question is this: when is the full automorphism group of Cay(G, S) isomorphic to G? Here, the Cayley graph admits no other automorphisms than those induced by right multiplication by elements of G, and is then called a graphical regular representation (or GRR) of G. An initial study of such graphs (considering what happens when the index |Aut Cay(G, S):G| is as small as possible) was undertaken by Imrich and Watkins [24], and all finite groups admitting a GRR were determined by Hetzel (in the solvable case) and Godsil (in the non-solvable case); see [19]. In fact the only finite groups without a GRR are those with the property that every subset C which is closed under inversion is fixed by some non-trivial group automorphism, and Babai and Godsil have conjectured that unless the finite group G belongs to a known class of exceptions, almost all Cayley graphs of G have G as their full automorphism group; see [4].

More general questions about the symmetry groups of Cayley graphs have been considered by Jajcay [25, 26], Marušič [31], Potočnik [33], and Fang, Praeger and Wang [18].

At something of the opposite extreme to GRRs is the question of just how large the automorphism group of a Cayley graph can be.

In particular, Caiheng Li has studied the question of when a Cayley graph can be sarc-transitive for some s ≥ 3. In [30] he constructed examples of 4-arc-transitive Cayley graphs of valency q + 1 for every prime-power q (with base group G a subgroup of order 2(q^{2} + q + 1) in the automorphism group PGL(3, q) of a Desarguesian projective plane of order q). Furthermore, he also proved in [30] that for every integer k ≥ 3 with k ≠ 7, and every s ∈ {3, 4, 5, 7}, there exists a finite set G_{s,k} of s-arc-transitive Cayley graphs of valency k such that every s-arc-transitive Cayley graph of valency k is a ‘normal cover’ of one of the graphs in G_{s,k}. But in [30], however, Caiheng Li wrote “We do not know any other examples of 4-transitive Cayley graphs, and we do not have any examples of 5- or 7-transitive Cayley graphs at all”.

In Section 2, we will show how to construct examples of 5-arc-transitive cubic Cayley graphs, in a way that proves there exist infinitely many of them. In fact we will show that every 5-arc-transitive cubic Cayley graph Cay(G, S) is a cover of one of just six such graphs, which are the only examples with G core-free in Aut Cay(G, S). The smallest is the Biggs-Conway graph, which is a 5-arc-transitive cubic graph on 2352 vertices [6], and turns out to be a Cayley graph. Two of the other examples are non-isomorphic cubic Cayley graphs for the alternating group A_{47}, which have been discovered independently by Shang Jin Xu, Xin Gui Fang, Jie Wang and Ming Yao Xu in the context of arc-transitive Cayley graphs for finite simple groups [45, 46].

The approach we take in Section 2 can be applied also to the case of 7-arc-transitive Cayley graphs, and we do this to show to construct infinitely many 4-valent examples of in Section 3, and infinitely many examples of valency 1 + 3^{t} (for each t ≥ 1) in Section 4.

In all these cases, the construction is based on the observation that if the symmetric graph X is a Cayley graph, then its automorphism group A = Aut X has a subgroup G that acts regularly on vertices, and so A is expressible as a complementary product A = GH = HG with G ∩ H = {1}, where H is the stabilizer of a vertex of X. The graph X itself can be defined using the natural action of A on cosets of H. On the other hand (and importantly), in the natural action of A on cosets of G, the subgroup H acts fixed-point-freely, so that possibilities for A can be obtained by combining regular actions of H together in a particular way, with the group G then taken as the stabilizer of a point.

The other questions we answer in this paper concern the embedding of an arc-transitive graph into a surface, in such a way that the resulting structure retains a high degree of symmetry. Formally, a map is a 2-cell embedding of a connected graph or multigraph into a closed surface, so that the faces (the connected components of the complementary space) are homeomorphic to unit disks. The map M is called orientable or non-orientable according to whether the supporting surface is orientable or non-orientable, and similarly the Euler characteristic χ and the genus γ of M are inherited from this surface.

An automorphism of a map M is any permutation of its edges which preserves incidence (with vertices and faces), and under composition, such automorphisms form a group denoted by Aut M. If the surface is orientable, then the automorphisms preserving the orientation form a subgroup of index 1 or 2 in Aut M, denoted by Aut^{o}M. By connectedness, it is not difficult to see that every automorphism of a map M is uniquely determined by its effect on any given incident vertex-edge-face triple, or flag (or blade), and it follows that |Aut M| ≤ 4|E| where E is the edge-set of the underlying graph or multigraph. Similarly, when M is orientable, |Aut^{o}M| ≤ 2|E|.

A map M is called regular if Aut M has a single orbit on the blades of M, for then Aut M acts regularly (sharply-transitively) on the blade-set. An orientable map M is called orientably-regular, or sometimes rotary, if Aut^{o}M has a single orbit transitive on the incident vertex-edge pairs (the arcs) of M; if such a map M admits an orientationreversing automorphism (in which case Aut^{o}(M) has index 2 in Aut(M)), then M is reflexible, and otherwise M is said to be chiral. Note that the underlying graph of any regular or orientably-regular map M has to be arc-transitive; also the stabilizer in Aut(M) of a vertex or face is dihedral when M is regular, but cyclic when M is chiral. Other terms used occasionally for a such maps are symmetrical maps, or symmetric embeddings of the underlying graphs; see [5] for example.

The automorphism group of any regular or orientably-regular map M acts transitively on faces and on edges of M, so all faces have the same number of edges (say p) and all vertices have the same valency (say q), and then M is said to have type {p, q}. The most famous examples are those coming from the Platonic solids, viewed as embeddings in the sphere of the tetrahedron (of type {3, 3}), cube (type {4, 3}), octahedron (type {3, 4}), dodecahedron (type {5, 3}) and icosahedron (type {3, 5}). On the torus (genus 1), there are three possible types: regular triangulations and their honeycomb duals (of type {3, 6} and {6, 3} respectively), and quadrangulations (of type {4, 4}); see [15, Chapter 8].

In their work on a family of imprimitive symmetric graphs [34], Cheryl Praeger and Sanming Zhou encountered orientably-regular maps with 3-valent underlying graphs, and identified examples where the underlying graph X is s-arc-regular for s = 2, 3 or 4, but were unable to find examples where X is 1- or 5-arc-regular.

In answer to their questions, in Section 5 we give characterisations of finite symmetric cubic graphs that can be embedded on some surface as a regular or orientably-regular map, and show that there are infinitely many examples where the graph is 1- or 5-arc-regular. A key observation is similar to the one made for symmetries of Cayley graphs, namely that if X is an s-arc-regular cubic graph which admits such an embedding, then its automorphism group Aut X has a subgroup G of specified index that acts transitively on the arcs of X and induces the automorphism group of the resulting map. Remarkably, in the case where X is 5-arc-regular, again all examples are covers of the Biggs-Conway graph.

2 5-arc-transitive cubic Cayley graphs

By the work of Tutte [39, 40], Goldschmidt [20], Djoković and Miller [16] and others, it is well known that the automorphism group of any finite 5-arc-transitive cubic graph is a homomorphic image of one particular infinite (but finitely-presented) group G_{5}. In fact G_{5} is an amalgamated free product of two small finite groups: S_{4} × C_{2} of order 48 (stabilizing a vertex) and a semi-direct product D_{8} ⋊ C_{2} of order 32 (stabilizing an edge), with the subgroup D_{4} × C_{2} of order 16 (stabilizing an arc) amalgamated. Moreover, any finite quotient of this group in which the orders of these stabilizers are preserved is the full automorphism group of a 5-arc-transitive cubic graph, as explained below.

We will use a presentation introduced in [13] for the group G_{5}, namely the following:

G_{5} = ⟨ h, p, q, r, s, a | h^{3} = p^{2} = q^{2} = r^{2} = s^{2} = a^{2} = 1,
[p, q] = [p, r] = [p, s] = [q, r] = [q, s] = 1, (rs)^{2} = pq,
h^{−1}ph = p, h^{−1}qh = r, h^{−1}rh = pqr, shs = h^{−1}, ap = qa, ar = sa ⟩.

Here the stabiliser of a vertex may be taken as the image of the subgroup ⟨h, p, q, r, s⟩, and the stabilizer of an arc (incident with that vertex) as the image of ⟨p, q, r, s⟩, with the image of the element a reversing the arc.

If θ: G_{5} → A is a group epimorphism, and H denotes the θ-image of ⟨h, p, q, r, s⟩, and (by abuse of notation) we also let a denote its θ-image in A, then we may define a 3-valent double coset graph X = Γ(A, H, a) with automorphism group A as follows: vertices of X are the cosets of H in A, and vertex Hx is adjacent to vertex Hy whenever xy^{−1} ∈ HaH. The group A acts on X by right multiplication, and if the restriction of θ to ⟨h, p, q, r, s⟩ is faithful then this action is 5-arc-transitive; see [10] or [13] for further details.

Now let X = Cay(G, S) be a finite 5-arc-transitive cubic Cayley graph, and suppose θ: G_{5} → A is a corresponding epimorphism, where A = Aut X. Since X is a Cayley graph for G, its automorphism group A contains G as a vertex-regular subgroup, complementary to the vertex-stabilizer H ≅ S_{4} × C_{2}, and hence of index |A: G| = |H| = |S_{4} × C_{2}| = 48 in A. Furthermore, in the natural action of A on right cosets of G, the subgroup H acts faithfully, with a single orbit of length 48, and therefore regularly. The pre-image of G under the epimorphism θ: G_{5} → A is then a subgroup L of index 48 in G_{5}, complementary to ⟨h, p, q, r, s⟩, and the natural action of G_{5} on the right cosets of L is equivalent to the action of A = θ(G_{5}) on the coset space (A: G). In particular, if K is the core of L (the intersection of all conjugates of L) in G_{5}, then A has a quotient A/θ(K) isomorphic to the quotient G_{5}/K, and of course K contains ker θ.

Conversely, suppose L is any subgroup of index 48 in G_{5} complementary to ⟨h, p, q, r, s⟩. Then the natural action of G_{5} on the right cosets of L gives a homomorphism θ: G_{5} → S_{48}, the image of which is a group A expressible as the product GH of the images G and H of the complementary subgroups L and ⟨h, p, q, r, s⟩ respectively. As G is the stabilizer in A of a point, and the restriction of θ to ⟨h, p, q, r, s⟩ is faithful, the subgroups G and H are complementary in A. In particular, it follows that G acts faithfully on right cosets of H, and therefore the graph X = Γ(A, H, a) is a 5-arc-transitive Cayley graph for the group G.

Moreover, if N is any normal subgroup of finite index in G_{5}, and contained in such a subgroup L, then N ∩ ⟨h, p, q, r, s⟩ is trivial, and so by the same kind of argument, the finite group G_{5}/N is the automorphism group of a 5-arc-transitive Cayley graph for the group L/N. Also since N ⊆ K ⊂ L where K is the core of L in G_{5}, this graph is a cover of the corresponding Cayley graph for the L/K (a core-free subgroup of G/K).

Thus every finite 5-arc-transitive cubic Cayley graph is a cover of one that is obtainable (in the way described above) from a subgroup L of index 48 in G_{5} complementary to ⟨h, p, q, r, s⟩. We can use this observation to prove that examples exist, to find all the minimal ones (of which all others are covers), and prove that there are infinitely many.

Before proceeding, we make some other observations about the natural action of the group G_{5} on the right coset space (G_{5} :L), or equivalently, the action of the group A on the right coset space (A: G). First, we know that the vertex-stabilizer ⟨h, p, q, r, s⟩ ≅ S_{4} × C_{2} acts regularly on the coset space, with a single orbit of length 48, and hence that the action of G_{5} = ⟨h, p, q, r, s, a⟩ is completely determined by this regular permutation representation of ⟨h, p, q, r, s⟩ and the permutation induced by its other generator a. Next, the coset space breaks up into three orbits of the arc-stabilizer ⟨p, q, r, s⟩, each of length 16, and it is easy to see from the relations ap = qa and ar = sa (which show that the involution a normalizes ⟨p, q, r, s⟩) that a induces a permutation of the three orbits of ⟨p, q, r, s⟩. Indeed up to equivalence there are just two possibilities for this permutation, as illustrated in Figure 1:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16  16  16  16  16  16^{^{.}. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . . . . .. . . . . . .. . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}  ^{^{.}. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . . . . .. . . . . . .. . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}  ^{^{.}. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . . . . .. . . . . . .. . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}  ^{^{.}. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . . . . .. . . . . . .. . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}  ^{^{.} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}

Fig. 1: The two possibilities for the effect of a on the orbits of ⟨p, q, r, s⟩

Note that the action of the generator a is completely determined by its effect on just three points, one from each of these three sub-orbits: once the image of a point x under a is known, so are the images of x^{p} (since (x^{p})^{a} = (x^{a})^{q}), and x^{q} (since (x^{q})^{a} = (x^{a})^{p}), and x^{r} (since (x^{r})^{a} = (x^{a})^{s}), and so on. In fact, in the second of the two possibilities illustrated in Fig.1, the action of a is determined by its effect on just two points.

The subgroup L, which is the stabilizer of a point in this representation of G_{5} on 48 points, can therefore be generated by just two or three elements.

For example, let us start with the following as the regular representation of ⟨h, p, q, r, s⟩, in which the orbits of ⟨p, q, r, s⟩ are the mod 3 residue classes {3k + i : 0 ≤ k < 16}, for i = 1, 2, 3:

h ↦ (1, 2, 3)(4, 5, 6)(7, 8, 9)(10, 11, 12)(13, 14, 15)(16, 17, 18)(19, 20, 21)(22, 23, 24)(25, 27, 26)
(28, 30, 29)(31, 33, 32)(34, 36, 35)(37, 39, 38)(40, 42, 41)(43, 45, 44)(46, 48, 47),
p ↦ (1, 4)(2, 5)(3, 6)(7, 10)(8, 11)(9, 12)(13, 16)(14, 17)(15, 18)(19, 22)(20, 23)(21, 24)(25, 28)

(26, 29)(27, 30)(31, 34)(32, 35)(33, 36)(37, 40)(38, 41)(39, 42)(43, 46)(44, 47)(45, 48),

q ↦ (1, 7)(2, 23)(3, 15)(4, 10)(5, 20)(6, 18)(8, 17)(9, 21)(11, 14)(12, 24)(13, 19)(16, 22)(25, 31)

(26, 47)(27, 39)(28, 34)(29, 44)(30, 42)(32, 41)(33, 45)(35, 38)(36, 48)(37, 43)(40, 46),

r ↦ (1, 13)(2, 8)(3, 24)(4, 16)(5, 11)(6, 21)(7, 19)(9, 18)(10, 22)(12, 15)(14, 20)(17, 23)(25, 46)

(26, 38)(27, 33)(28, 43)(29, 41)(30, 36)(31, 40)(32, 44)(34, 37)(35, 47)(39, 45)(42, 48),

s ↦ (1, 25)(2, 26)(3, 27)(4, 28)(5, 29)(6, 30)(7, 31)(8, 32)(9, 33)(10, 34)(11, 35)(12, 36)(13, 37)

(14, 38)(15, 39)(16, 40)(17, 41)(18, 42)(19, 43)(20, 44)(21, 45)(22, 46)(23, 47)(24, 48).

This representation can be extended to one of the group G_{5} = ⟨h, p, q, r, s, a⟩ by letting

\begin{aligned}a ↦ & (4, 7)(5, 23)(6, 15)(8, 26)(9, 42)(11, 47)(12, 30)(13, 25)(14, 44)(16, 31)(17, 29)(19, 28) \\ & (21, 39)(22, 34)(24, 27)(32, 38)(33, 48)(37, 46). \end{aligned}

Note that a preserves each of the three residue classes {3k + i : 0 ≤ k < 16}. Also a fixes the three points 1, 2 = 1^{h} and 3 = 1^{h^{−1}}, or equivalently, the point 1 is fixed by each of a, hah^{−1} and h^{−1}ah. Moreover, specifying that a should fix the three points 1, 2 and 3 (one from each orbit of ⟨p, q, r, s⟩) is enough to completely determine the permutation induced by a on these 48 points, and hence completely determine the representation, and it follows that the subgroup L is generated by the three elements a, hah^{−1} and h^{−1}ah.

In this case, the permutations induced by h, p, q, r, s and a generate a group of order 112896, isomorphic to a subgroup of index 2 in the wreath product PGL(2, 7) ≀ S_{2}, and the corresponding graph is the Biggs-Conway graph on 2352 vertices — see [6]. Accordingly, the Biggs-Conway graph is a 5-arc-transitive Cayley graph, which provides a positive answer to one of the questions Caiheng Li raised in [30].

But furthermore, we can show that there are infinitely many covers of this graph that are also 5-arc-transitive Cayley graphs, as follows. The kernel of the epimorphism from G_{5} to the automorphism group of the Biggs-Conway graph is a normal subgroup K of index 112896 in G_{5}, being the core of the subgroup L = ⟨h, hah^{−1}, h^{−1}ah⟩, and K itself is generated by conjugates of the element (ha)^{4}(h^{−1}a)^{4}ha(h^{−1}a)^{2}(ha)^{2}h^{−1}a. These facts can be verified with the help of the Magma system [7].

Also by the Reidemeister-Schreier process (implemented as the Rewrite command in Magma), we find that K has abelianisation K/[K, K] ≅ ℤ^{1177}. (Note that computation of this abelianisation is not easy because of the large index |G_{5} : K|; but it is relatively easy to see that K is contained in the subgroup L = ⟨h^{−1}aha, hah^{−1}a⟩, which has index 96 in G_{5} and has abelianisation L/[L, L] ≅ ℤ^{2}, and then since [K, K] ⊂ [L, L], it follows that [K, K] has infinite index in L, and therefore infinite index in K.)

Now since K has infinite abelianisation, it follows that for every positive integer k, the group G_{5} contains a normal subgroup N_{k} = [K, K]K^{k} of index k^{1177} in K, with quotient G_{5}/N_{k} of order 112896k^{1177}, which is then the automorphism group of a 5-arc-transitive cubic graph of order 2352k^{1177} that is a cover of the Biggs-Conway graph. Moreover, as N_{k} ⊆ K ⊂ L, and L is complementary to ⟨h, p, q, r, s⟩ in G_{5}, this cover is a Cayley graph for the group L/N_{k}.

Thus we have infinitely many finite 5-arc-transitive 3-valent Cayley graphs.

Finally, there are five other possibilities for the subgroup L, up to conjugacy in the group G_{5}. These can be found either by using the LowIndexSubgroups command in Magma (and checking subgroups for complementarity with ⟨h, p, q, r, s⟩ in G_{5}), or by enumerating the possibilities for the images of the points 1, 2 and 3 (in the regular representation of ⟨h, p, q, r, s⟩) under the permutation induced by the generator a.

The six possibilities may be summarised as follows:

(1) L = ⟨ a, hah^{−1}, h^{−1}ah ⟩, with a ↦ (4, 7)(5, 23)(6, 15)(8, 26)(9, 42)(11, 47)(12, 30)(13, 25) (14, 44)(16, 31)(17, 29)(19, 28)(21, 39)(22, 34)(24, 27)(32, 38)(33, 48)(37, 46), giving G_{5}/K isomorphic to a subgroup of index 2 in the wreath product PGL(2, 7)≀S_{2}, and G = L/K isomorphic to a subdirect product of D_{7} and PGL(2, 7), of order 2352;

(2) L = ⟨ a, hah^{−1}, prh^{−1}ah ⟩, with a ↦ (3, 18)(4, 7)(5, 23)(8, 26)(9, 27)(11, 47)(12, 39)(13, 25) (14, 44)(16, 31)(17, 29)(19, 28)(21, 30)(22, 34)(24, 42)(32, 38)(36, 45)(37, 46), giving G_{5}/K isomorphic to a subgroup of index 2 in the wreath product S_{24} ≀ S_{2}, and G = L/K isomorphic to a subdirect product of subdirect product of S_{23} and S_{24}, of order (23! × 24!)/2;

(3) L = ⟨ a, hah, (hah)^{−1} ⟩, with a ↦ (2, 3)(4, 7)(5, 15)(6, 23)(8, 27)(9, 44)(11, 39)(12, 29)(13, 25) (14, 42)(16, 31)(17, 30)(18, 20)(19, 28)(21, 47)(22, 34)(24, 26)(32, 33) (35, 45)(36, 41)(37, 46)(38, 48), giving G_{5}/K isomorphic to a subgroup of index 2 in the wreath product ((C_{3})^{7} ⋊ PGL(2, 7)) ≀ S_{2}, and G = L/K isomorphic to a subdirect product of (C_{3})^{6} ⋊ (C_{7} :C_{6}) and (C_{3})^{7} ⋊ PGL(2, 7), of order 11249543088;

(4) L = ⟨ a, phah, (phah)^{−1} ⟩, with a ↦ (2, 15)(3, 5)(4, 7)(6, 20)(8, 39)(9, 47)(11, 27)(12, 26)(13, 25) (14, 30)(16, 31)(17, 42)(18, 23)(19, 28)(21, 44)(22, 34)(24, 29)(32, 45) (33, 35)(36, 38)(37, 46)(41, 48), giving G_{5}/K isomorphic to the alternating group A_{48}, and G = L/K isomorphic to the alternating group A_{47};

(5) L = ⟨ a, qrhah, (qrhah)^{−1} ⟩, with a ↦ (2, 18)(3, 20)(4, 7)(5, 6)(8, 42)(9, 26)(11, 30)(12, 47) (13, 25)(14, 27)(15, 23)(16, 31)(17, 39)(19, 28)(21, 29)(22, 34)(24, 44) (32, 48)(33, 38)(35, 36)(37, 46)(41, 45), giving G_{5}/K isomorphic to a subgroup of index 2 in the wreath product PGL(2, 23)≀S_{2}, and G = L/K isomorphic to a subdirect product of C_{23} :C_{22} and PGL(2, 23), of order 3072432;

(6) L = ⟨ a, rhah, (rhah)^{−1} ⟩, with a ↦ (2, 42)(3, 14)(4, 7)(5, 30)(6, 11)(8, 18)(9, 32)(12, 41) (13, 25)(15, 17)(16, 31)(19, 28)(20, 27)(21, 35)(22, 34)(23, 39)(24, 38) (26, 48)(29, 36)(33, 44)(37, 46)(45, 47), giving G_{5}/K isomorphic to the alternating group A_{48}, and G = L/K isomorphic to the alternating group A_{47}.

Note that in the first two cases, the permutation induced by a preserves each of the three orbits of ⟨p, q, r, s⟩, while in the other four cases, it preserves one and interchanges the other two. Also the two graphs with G ≅ A_{47} are the only examples for which G is simple, and these have been discovered independently by Shang Jin Xu, Xin Gui Fang, Jie Wang and Ming Yao Xu [45, 46].

Moreover, it is not difficult to show that each of the resulting six Cayley graphs is a cover of infinitely many other finite 5-arc-transitive 3-valent Cayley graphs, because each subgroup L has either infinite abelianisation or a subgroup of index 2 (and index 96 in G_{5}) with infinite abelianisation. Another (but equivalent) way to see this is to observe that copies of the permutation representation of G_{5} on cosets of L can be glued together (as in the construction given in [9]) to give transitive but imprimitive permutation representations of G_{5} of arbitrarily large degree, all having the property that the stabilizer of a point is complementary to the image of ⟨h, p, q, r, s⟩.

In summary, we have the following:

Theorem 2.1 There are infinitely many 5-arc-transitive 3-valent finite Cayley graphs. Moreover, every such graph is a cover of one of just six examples, these being the only examples for which the underlying group is core-free in the automorphism group of the graph :

(a) The Biggs-Conway graph, which is a Cayley graph for a subdirect product of D_{7} and PGL(2, 7), of order 2352, with automorphism group a subgroup of index 2 in the wreath product PGL(2, 7) ≀ S_{2} ;

(b) A Cayley graph for a subdirect product of C_{23} :C_{22} and PGL(2, 23), of order 3072432, with automorphism group a subgroup of index 2 in the wreath product PGL(2, 23)≀S_{2} ;

(c) A Cayley graph for a subdirect product of (C_{3})^{6} ⋊ (C_{7} : C_{6}) and (C_{3})^{7} ⋊ PGL(2, 7), of order 11249543088, with automorphism group a subgroup of index 2 in the wreath product ((C_{3})^{7} ⋊ PGL(2, 7)) ≀ S_{2} ;

(d) A Cayley graph for a subdirect product of S_{23} and S_{24}, of order (23! × 24!)/2, with automorphism group a subgroup of index 2 in the wreath product S_{24} ≀ S_{2} ;

(e) Two Cayley graphs for the alternating group A_{47}, each with automorphism group A_{48}.

3 7-arc-transitive quartic Cayley graphs

This case is very similar to that of the last one.

By theorems of Weiss [42, 44], the automorphism group of every finite 7-arc-transitive finite 4-valent graph is a homomorphic image of the group R_{4,7} with presentation

R_{4,7} = ⟨ h, p, q, r, s, t, u, v, b | 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, [s, t] = p,
[p, q] = [p, r] = [p, s] = [p, t] = [q, r] = [q, s] = [q, t] = [r, s] = [r, t] = 1,
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, bh^{2}b = h^{2}v ⟩.

Here the stabiliser of a vertex may be taken as the image of the subgroup ⟨h, p, q, r, s, t, u, v⟩, with the image of the element b reversing an arc. The subgroup ⟨h, p, q, r, s, t, u, v⟩ in this case is isomorphic to an extension of a group of order 3^{5} by GL_{2}(3), and has order 11664.

If θ: R_{4,7} → A is any group epimorphism, and b and H denote the θ-images of b and ⟨h, p, q, r, s, t, u, v⟩, then we may define a double coset graph X = Γ(A, H, b) on which A acts, in the same way as before: vertices of X are the cosets of H in A, and vertex Hx is adjacent to vertex Hy whenever xy^{−1} ∈ HbH. The group A acts on X by right multiplication, and if the restriction of θ to ⟨h, p, q, r, s, t, u, v⟩ is faithful then X is 4-valent and the action of A on X is 7-arc-transitive.

The graph X is a Cayley graph if and only if the group A contains a vertex-regular subgroup G of index |A: G| = |H| = 11664, complementary to the vertex-stabilizer H in A. In that case, the pre-image of G under the epimorphism θ is a subgroup L of index 11664 in R_{4,7}, complementary to ⟨h, p, q, r, s, t, u, v⟩, and with core K containing ker θ, and so on, as in the previous section. Every finite 7-arc-transitive 4-valent Cayley graph is a cover of one obtainable from a subgroup L of R_{4,7} in this way.

Also as previously, the vertex-stabilizer ⟨h, p, q, r, s, t, u, v⟩ ≅ (C_{3})^{5} ⋊ GL_{2}(3) acts regularly on the right coset space (R_{4,7} :L), with a single orbit of length 11664, which breaks up into four orbits of the arc-stabilizer ⟨p, q, r, s, t, u, v, h^{2}⟩ ≅ (C_{3})^{5} ⋊ A_{4}, each of length 2916. The involution b normalizes ⟨p, q, r, s, t, u, v, h^{2}⟩, so induces a permutation of these four orbits, and its effect on the coset space (R_{4,7} : L) is uniquely determined by its effect on any four points from different orbits of ⟨p, q, r, s, t, u, v, h^{2}⟩. Up to rearrangement of the four orbits, there are just three possibilities, as illustrated in Figure 2:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2916  2916  2916  2916^{^{.}. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . . . . .. . . . . . .. . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}  ^{^{.}. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . . . . .. . . . . . .. . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}  ^{^{.}. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . . . . .. . . . . . .. . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}  ^{^{.}. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . . . . .. . . . . . .. . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2916  2916  2916  2916^{^{.}. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . . . . .. . . . . . .. . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}  ^{^{.} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}  ^{^{.}. . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . .. . . . . . . . . .. . . . . . .. . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .  .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2916  2916  2916  2916^{^{.} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}  ^{^{.} . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}^{^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}^{.}}}

Fig. 2: The three possibilities for the effect of b on the orbits of ⟨p, q, r, s, t, u, v, h^{2}⟩

By computation (enumerating the possibilities for the images of four points from different orbits of ⟨p, q, r, s, t, u, v, h^{2}⟩ under the permutation induced by the generator b on the coset space (R_{4,7} :L)), we have found there are exactly 968 conjugacy classes of subgroups L of index 11664 in R_{4,7} that are complementary to ⟨h, p, q, r, s, t, u, v⟩.

One example is the subgroup L = ⟨ b, hbh^{−1}, uhbh^{−1}u^{−1}, u^{−1}hbh^{−1}u ⟩. In this case the permutation induced by b preserves each of the four orbits of ⟨p, q, r, s, t, u, v, h^{2}⟩ on the coset space (R_{4,7} :L), the quotient R_{4,7}/K by the core K of L in R_{4,7} is isomorphic to the alternating group A_{11664}, and the resulting graph is a 7-arc-transitive 4-valent Cayley graph for the group L/K ≅ A_{11663}. Moreover, the subgroup L here has many subgroups with infinite abelianisation (such as a subgroup of index 2 generated by hbh^{−1}b, pt^{−1}hbhbh^{−1}svb, qh^{−1}bhbtq^{−1}hvh^{−1} and v^{−1}s^{−1}hb^{−1}h^{−1}b^{−1}h^{−1}tp^{−1}b), and hence (as previously) this graph has infinitely many finite covers that are themselves 7-arc-transitive 4-valent Cayley graphs.

The infinitude of such graphs can also be proved by gluing together copies of the regular permutation representation of ⟨h, p, q, r, s, t, u, v⟩ ≅ (C_{3})^{5} ⋊ GL_{2}(3) of degree 11664 (as in the construction given in [14]) to give transitive but imprimitive permutation representations of R_{4,7} of arbitrarily large degree, in which the stabilizer of a point is complementary to the image of ⟨h, p, q, r, s, t, u, v⟩.

Thus we have the following:

Theorem 3.1 There are infinitely many 7-arc-transitive 4-valent finite Cayley graphs. Moreover, every such graph is a cover of one of 968 examples (these being the only examples for which the underlying group is core-free in the automorphism group of the graph).

One remarkable thing about the 968 basic examples is that in all but one case, the permutation group induced by R_{4,7} on the coset space (R_{4,7} : L) is the alternating group A_{11664}. In the non-alternating case, a representative of the conjugacy class of possibilities for the subgroup L is the subgroup generated by b, hbh^{−1}, uhbv^{−1}h^{−1}u^{−1} and u^{−1}hbt^{−1}hv^{−1}. Here the permutation group induced on cosets is isomorphic to a subgroup of index 2 in the group (A_{8} ≀ S_{2}) ≀ S_{729}, of order ((8!)/2)^{1458}2^{728}729!, having two systems of imprimitivity: one with 729 blocks of size 16 (permuted naturally by the quotient S_{729}) and the other with 1458 blocks of size 8 (permuted naturally by the quotient isomorphic to a subgroup of index 2 in S_{2} ≀ S_{729}). These facts can verified with the help of the Magma system (and some additional analysis).

4 7-arc-transitive Cayley graphs of valency 1+3^{t}

As explained in the Introduction, it has been proved by Weiss that for every positive integer t, there exists a 7-arc-transitive finite graph of valency 1 + 3^{t}, namely the generalized hexagon over GF(3^{t}). Details may be found in [43, 44, 37]. We will now prove there are infinitely many such graphs for each t, and indeed that there are infinitely many finite 7-arc-transitive Cayley graphs of valency 1+3^{t}, for each t.

Just as in the case t = 1 (for 4-valent graphs), there exists a finitely-presented group R_{1+3^{t},7} with the property that examples of such graphs can be constructed from its nondegenerate finite quotients. The group R_{1+3^{t},7} is an amalgamated free product of two subgroups V and E acting as the stabilizers of a vertex v and an edge e, respectively, with intersection V ∩ E acting as the stabilizer of the arc (v, e). Also R_{1+3^{t},7} is generated by V and an arc-reversing element b ∈ E such that b normalizes V ∩ E and b^{2} ∈ V ∩ E. These groups V and E (and their intersection V ∩ E) may be taken as (isomorphic copies of) the corresponding stabilizers in any 7-arc-transitive subgroup of the full automorphism group of the generalized hexagon over GF(3^{t}). The order of the element b is 2m, where m is the largest power of 2 dividing t.

(To see these things requires some technical work involving details from [37, Sections 4 and 29]. For each positive integer t there is a unique generalized hexagon over a field F_{q} of order q = 3^{t}, as defined in [37, 16.8]. This is 7-arc-transitive and has valency 1+3^{t}. In its full automorphism group, the edge-stabilizer E can be taken as an extension of the group of order q^{6} generated by the elements U_{i} for 1 ≤ i ≤ 6 (as defined in [37, 5.1]) by a semi-direct product of Aut(F_{q}) and ℤ_{q−1}×ℤ_{q−1}. The vertex-stabilizer V is a semi-direct product of the group of order q^{5} generated by the elements U_{1}, U_{2}, …, U_{5} by Aut(F_{q}) P GL(2, F_{q}). The arc-reversing automorphism b can be chosen as the automorphism taking x_{1}(a) ↦ x_{6}(a^{3}), x_{2}(a) ↦ x_{5}(−a), x_{3}(a) ↦ x_{4}(−a^{3}), x_{4}(a) ↦ x_{3}(−a), x_{5}(a) ↦ x_{2}(−a^{3}) and x_{6}(a) ↦ x_{1}(a), in the notation of [37, Section 29].)

If θ: R_{1+3^{t},7} → A is a group epimorphism, and b and H denote the θ-images of b and V respectively, then we may define a double coset graph X = Γ(A, H, b) on which A acts, in the same way as previously. In particular, if the restriction of θ to V is faithful then X is (1+3^{t})-valent and the action of A on X is 7-arc-transitive.

Further, the graph X = Γ(A, H, b) is a Cayley graph if and only if the group A contains a vertex-regular subgroup G of index |A:G| = |H|, complementary to the vertex-stabilizer H in A, or equivalently, the pre-image of G under θ is a subgroup L of index |V | in R_{1+3^{t},7}, complementary to V. In this case, as before, the vertex-stabilizer V acts regularly on the right coset space (R_{1+3^{t},7} :L), with a single orbit of length |V |, which breaks up into 1+3^{t} orbits of the arc-stabilizer V ∩ E, each of length |V |/(1+3^{t}). The element b, normalizing V ∩ E, induces a permutation of these orbits, and its effect on the coset space (R_{1+3^{t},7} :L) is uniquely determined by its effect on any 1+3^{t} points from different orbits of V ∩ E.

The generalized hexagons themselves are not Cayley graphs, but they can be used to construct examples of 7-arc-transitive Cayley graphs, as follows.

First, take the regular representation of the group V, of degree n = |V |, and break it into 1+3^{t} orbits of the subgroup V ∩ E (each of length |V ∩ E| = n/(1+3^{t})). Now extend this representation of V to a transitive permutation representation of R_{1+3^{t},7} = ⟨V, E⟩ of the same degree n, by a suitable definition of a permutation for b. Since V ∩ E has index 2 in ⟨V ∩ E, b⟩ = E, this can be done by forming orbits of E as unions of one or two orbits of V ∩ E (and hence of length |E| or |E|/2 = |V ∩ E|), in the same way that orbits of the image of V ∩ E are combined by the image of b to form orbits of the image of E in the full automorphism group of the generalized hexagon over GF(3^{t}).

Note that each choice of b is uniquely determined by its effect on any 1+3^{t} points from different orbits of V ∩ E, and induces a permutation of the 1+3^{t} orbits of |V ∩ E|, of order 1 or 2 (since b^{2} ∈ V ∩ E). In fact any permutation of order 1 or 2 on these 1+3^{t} orbits can be induced by a suitable choice of b (because the only significant requirement on b is the linkage of pairs of orbits of V ∩ E into orbits of E). Hence the number of ways of defining the effect of b is fixed for each t, but is at least equal to the number of involutions in S_{1+3^{t}}, which is a strictly increasing function of t.

In the resulting permutation representation of R_{1+3^{t},7} = ⟨V, b⟩ of degree n, the stabilizer of any point is complementary to the regular subgroup induced by V, and hence the resulting 7-arc-transitive graph of valency 1+3^{t} is a Cayley graph (for this point-stabilizer).

Corresponding to each such choice of b, the pre-image in R_{1+3^{t},7} of the point-stabilizer is is a subgroup of index n = |V | in R_{1+3^{t},7}, complementary to V, and this subgroup L can be generated by 1+3^{t} elements (or fewer in cases where the permutation b does not preserve all orbits of V ∩ E). Also the core of L in R_{1+3^{t},7} is the kernel of the resulting permutation representation R_{1+3^{t},7} (of degree |V |).

The above construction gives all the ‘minimal’ examples of 7-arc-transitive Cayley graphs of valency 1+3^{t}. As explained in previous sections, covers of these examples can be constructed by linking together copies of the regular permutation representation of the group V to produce transitive but imprimitive permutation representations of R_{1+3^{t},7} of increasing degree, each with point stabilizer contained in a subgroup of index n complementary to the image of V. It is not difficult to see that such representations can be constructed with degree 2kn (and in some cases degree kn) for any positive integer k, and hence each minimal example has infinitely many covers.

Thus we have the following:

Theorem 4.1 For every positive integer t, there are infinitely many 7-arc-transitive finite Cayley graphs of valency 1+3^{t}. Every such graph is a cover of one of a fixed number of examples (these being the only examples for which the underlying group is core-free in the automorphism group of the graph), and this number is a strictly increasing function of t.

5 Regular maps from arc-transitive cubic graphs

In this Section we give answers to the questions raised by Cheryl Praeger and Sanming Zhou, and more.

First, suppose M is a regular or orientably-regular map of type {k, 3}, with underlying graph X (which is necessarily 3-valent and arc-transitive). Then by standard theory of such maps (as explained in [11] for example), either Aut M or Aut^{o}M is generated by an element x of order k that preserves a face f, and an element x of order 3 that fixes a vertex v incident with f, such that xy reverses an edge {v, w} incident with v and f. Moreover, the map M is regular if and only if Aut M contains an element t of order 2 that inverts each of x and y by conjugation. In that case, the subgroup generated by x and y has index 1 or 2 in Aut M, depending on whether or not the map is orientable, and the dihedral subgroups ⟨x, t⟩ and ⟨y, t⟩ are the stabilizers in Aut M of the face f and the vertex v. On the other hand, if M is chiral, then ⟨x, y⟩ = Aut^{o}M = Aut M, and the stabilizers of f and v are the cyclic subgroups generated by x and y.

Now suppose M is a regular or orientably-regular map whose underlying graph X is 3-valent and 1-arc-regular. Then the automorphism group A of the graph X is generated by an element h of order 3 that fixes a vertex v, and an element a of order 2 that reverses an arc (v, w) incident with v; see [16] or [13]. The group A must also be the full automorphism group of M (since the latter has to be isomorphic to a subgroup of Aut X = A), with y = h generating the stabilizer of the vertex v and x = (ha)^{−1} = ah^{−1} generating the stabilizer of a face f incident with the edge {v, w}. In particular, the order of ha = x^{−1} is k where {k, 3} is the type of M. Moreover, M cannot be regular, and hence must be orientable, but chiral (irreflexible), because the stabilizer of a vertex in the automorphism group of X is cyclic, rather than dihedral (as it would have to be if M were regular).

Conversely, if X is any finite connected 1-arc-regular cubic graph, then X can be so embedded in some orientable surface as a chiral map M of type {k, 3}, where k is the order of ha for some generating pair (h, a) for A = Aut X satisfying h^{3} = a^{2} = 1. The genus γ of the supporting surface is given by the Euler-Poincaré formula

2 − 2γ = |A|(\frac{1}{3} − \frac{1}{2} + \frac{1}{k}) = |A|(\frac{6−k}{6k}).

It follows that there are lots of examples of such maps. They include infinitely many of the Coxeter ‘honeycomb’ maps {6, 3}_{(b,c)}, with hexagonal faces on the torus, for distinct positive integers b and c (see [15]), as well as many others on orientable surfaces of higher genera [11]. Examples of the latter include the chiral map C10.1 of type {8, 3} on an orientable surface of genus 10 (with underlying graph of order 144), and others obtainable from the census of small arc-transitive cubic graphs [12] (such as F448A, which gives a chiral map of type {7, 3} on an orientable surface of genus 33). Further infinite families are described in [8].

Next, suppose X is a finite 5-arc-transitive cubic graph, with automorphism group A (which must be an epimorphic image of the group G_{5} (as defined in Section 2)). If X can be embedded in some closed surface as a regular or orientably-regular map M, then M must be orientable but chiral (irreflexible), since A = Aut X contains no 2-arc-regular subgroup (and therefore no involutory automorphism that inverts the images of each of the canonical elements h and a by conjugation), by the work of Djoković and Miller [16]. Moreover, A contains a subgroup T that acts regularly on the arcs (ordered edges) of X. In particular, T must be complementary in A to the stabilizer of an arc of X, and as this arc-stabilizer is isomorphic to the direct product D_{4} × C_{2} (of index 3 in the vertex-stabilizer S_{4} × C_{2}), it follows that T has index |D_{4} × C_{2}| = 16 in A. Then further, the pre-image of T in G_{5} has to be a subgroup of index 16. But G_{5} has only one conjugacy class of subgroups of index 16, one of which is the subgroup S = ⟨ h, a ⟩. (This fact can be easily verified with the help of the LowIndexSubgroups procedure in Magma [7].) Moreover, the permutation group induced by G_{5} on cosets of this subgroup is a group of order 112896, and the corresponding graph is (again) the Biggs-Conway graph.

Conversely, if K is any normal subgroup of the group G_{5} contained in the subgroup S = ⟨ h, a ⟩, then G/K is the automorphism group of a finite 5-arc-transitive cubic graph X, which must be a cover of the Biggs-Conway graph. Moreover, its subgroup S/K is complementary to the arc-stabilizer (which is generated by the cosets of K containing p, q, r and s) and so acts regularly on the arcs of X, and it follows that X is the underlying graph of an orientably-regular map M, with S/K as its group of orientation-preserving automorphisms, and of type {k, 3} where k is the order of the coset Kha in S/K. As in the 1-arc-regular case, the genus γ of the supporting surface is given by the Euler-Poincaré formula 2 − 2γ = |S/K|(\frac{6−k}{6k}). Of course k must be divisible by 24 (the order of the image of ha in the automorphism group of the Biggs-Conway graph), with K being contained in the core of S in G_{5}.

Furthermore, as the subgroup S is isomorphic to the modular group (a free product of cyclic groups of orders 2 and 3), the group G_{5} has infinitely many (normal) subgroups of finite index contained in S, and so we have the following:

Theorem 5.1 There are infinitely many orientably-regular maps with a 3-valent 5-arc-transitive underlying graph. Moreover, the smallest example is an embedding of the Biggs-Conway graph (on 2352 vertices) into an orientable surface of genus 442 as a map of type {24, 3}, and every such map is a cover of this one, and chiral.

For completeness, we note what happens in the other cases of an arc-transitive finite connected cubic graph embedded as a regular or orientably-regular map M. Recall that every such graph X is s-arc-regular for some s ≤ 5 (by Tutte’s theorem), and that a partial presentation for its automorphism group A = Aut X is known. We have dealt with the cases s = 1 and s = 5 above.

When s = 2 or s = 3, the group A must be a quotient of one of the groups G_{2}^{1} and G_{3} defined in [13], since the only other possibility (involving the group G_{2}^{2}) gives no edgereversing involutions. Moreover, the map M is regular, since in each case A = Aut X contains a subgroup (of index 2 or 4 respectively) that acts regularly on the arcs of X, and is generated by an element h of order 3 that fixes a vertex v, and an element a of order 2 that reverses an arc (v, w) incident with v, and also contains an involutory element that inverts each of h and a by conjugation. In these two cases, the map M may be orientable or non-orientable.

On the other hand, when s = 4 the group Aut X must be a quotient of the group G_{4}^{1} given in [13], and also M must be orientable but chiral (irreflexible), since Aut X contains no 2-arc-regular subgroup, again by the work of Djoković and Miller [16]. Also the group A = Aut X must contain a subgroup T of index 8 that acts regularly on the arcs of X. In particular, the pre-image of T in G_{4}^{1} is uniquely determined up to conjugacy within the group G_{5}, and may be taken as the subgroup generated by the two elements h and a (as given in the presentation for G_{4}^{1} in [13]). The permutation group induced by G_{4}^{1} on the cosets of this subgroup is PGL(2, 7) ≅ PSL(3, 2), and the corresponding graph is the 14-vertex Heawood graph, which is the incidence graph of a projective plane of order two. The associated map is an embedding of the Heawood graph on the torus, of type {6, 3}, and the map M must be a cover of this one. Conversely, if K is any normal subgroup of the group G_{4}^{1} contained in the subgroup S = ⟨ h, a ⟩, then G/K is the automorphism group of a finite 4-arc-transitive cubic graph X, which must be a cover of the Heawood graph, embeddable as an orientably-regular but chiral map on a surface of the appropriate genus.

6 Final remarks

This paper would not be complete without mentioning some related work, namely on the embedding of Cayley graphs as regular or orientably-regular maps, now called regular Cayley maps. The special case of complete graphs was dealt with by Biggs and then James and Jones [27], and a study of the general case progressed by Škoviera and J. Širáň [35, 36]. Numerous articles have been published on the topic since then — but too many to mention here.

References

[1] B. Alspach, Isomorphism and Cayley graphs on abelian groups, in Graph symmetry (Montreal, PQ, 1996), Kluwer Acad. Publ. (Dordrecht), 1997, pp.1–22.

[2] L. Babai & P. Frankl, Isomorphisms of Cayley graphs I, in: Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), vol. 1, North-Holland (Amsterdam-New York), 1978, pp. 35–52.

[3] L. Babai & P. Frankl, Isomorphisms of Cayley graphs II, Acta Math. Acad. Sci. Hungar. 34 (1979), 177–183.

[4] L. Babai & C.D. Godsil, On the automorphism groups of almost all Cayley graphs, European J. Combin. 3 (1982), 9–15.

[5] N.L. Biggs, Cayley maps and symmetrical maps, Proc. Cambridge Philos. Soc. 72 (1972), 381–386.

[6] N.L. Biggs, A new 5-arc-transitive cubic graph, J. Graph Theory 6 (1982), 447–451.

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

[8] E. Bujalance, M. Conder and A. Costa, Pseudo-real Riemann surfaces and chiral regular maps, preprint.

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

[10] M.D.E. Conder, Group actions on graphs, maps and surfaces with maximum symmetry, in: Groups St Andrews 2001 in Oxford, London Math. Soc. Lecture Note Series, vol. 304, Cambridge University Press, 2003, pp. 63–91.

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

[12] M.D.E. Conder & P. Dobcsányi, Trivalent symmetric graphs on up to 768 vertices, J. Combin. Math. Combin. Computing 40 (2002), 41–63.

[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 & C.G. Walker, The infinitude of 7-arc-transitive graphs, Journal of Algebra 208 (1998), 619–629.

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

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

[17] E. Dobson, On the Cayley isomorphism problem, Discrete Math. 247 (2002), 107–116.

[18] X.G. Fang, C.E. Praeger & J. Wang, On the automorphism groups of Cayley graphs of finite simple groups, J. London Math. Soc. (2) 66 (2002), 563–578.

[19] C.D. Godsil, GRRs for nonsolvable groups, in: Algebraic methods in graph theory, Vol. I, II (Szeged, 1978), pp. 221–239, Colloq. Math. Soc. Jnos Bolyai, vol. 25, North-Holland, Amsterdam-New York, 1981.

[20] D.M. Goldschmidt, Automorphisms of trivalent graphs, Ann. of Math. 111 (1980), 377–406.

[21] P.R. Hafner, Large Cayley graphs and digraphs with small degree and diameter, in Computational algebra and number theory (Sydney, 1992), Kluwer Acad. Publ. (Dordrecht), 1995, pp.291–302.

[22] M-C. Heydemann, Cayley graphs and interconnection networks, in Graph symmetry (Montreal, PQ, 1996), Kluwer Acad. Publ. (Dordrecht), 1997, pp.167–224.

[23] M-C. Heydemann, N. Marlin & S. Pérennes, Complete rotations in Cayley graphs, European J. Combin. 22 (2001), 179–196.

[24] W. Imrich & M.E. Watkins, On automorphism groups of Cayley graphs. Period. Math. Hungar. 7 (1976), 243–258.

[25] R. Jajcay, Characterization and construction of Cayley graphs admitting regular Cayley maps, Discrete Math. 158 (1996), 151–160.

[26] R. Jajcay, The structure of the automorphism groups of Cayley graphs and maps, J. Algebraic Combin. 12 (2000), 73–84.

[27] L.D. James and G.A. Jones, Regular orientable imbeddings of complete graphs, J. Combinatorial Theory, Ser. B 39 (1985) 353–367.

[28] S. Lakshmivarahan, J.S. Jwo & S.K. Dhall, Symmetry in interconnection networks based on Cayley graphs of permutation groups: a survey, Parallel Comput. 19 (1993), 361–407.

[29] C.H. Li, On isomorphisms of finite Cayley graphs—a survey, Discrete Math. 256 (2002), 301–334.

[30] C.H. Li, Finite s-arc transitive Cayley graphs and flag-transitive projective planes, Proc. Amer. Math. Soc. 133 (2005), 31–4.

[31] D. Marušič, On 2-arc-transitivity of Cayley graphs, J. Combin. Theory Ser. B 87 (2003), 162–196.

[32] M. Muzychuk, An elementary abelian group of large rank is not a CI-group, Discrete Math. 264 (2003), 167–185.

[33] P. Potočnik, On 2-arc-transitive Cayley graphs of abelian groups, Discrete Math. 244 (2002), 417–421.

[34] C.E. Praeger & Sanming Zhou, Maps and imprimitive symmetric graphs, in preparation.

[35] M. Škoviera & J. Širáň, Regular maps from Cayley graphs I: Balanced Cayley maps, Discrete Math. 109 (1992), 265–276.

[36] M. Škoviera & J. Širáň, Regular maps from Cayley graphs II: Antibalanced Cayley maps, Discrete Math. 124 (1994), 179–191.

[37] J. Tits & R.M. Weiss, Moufang Polygons, Springer Verlag, 2002.

[38] V. Trofimov, On the action of a group on a graph, Acta Appl. Math. 29 (1992), 161–170.

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

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

[41] M.A. van Opstall & R. Veliche, Cubic graphs with most automorphisms, preprint 2006.

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

[43] Richard Weiss, Distance-transitive graphs and generalized polygons, Arch. Math. 45 (1985), 186–192.

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

[45] Shang Jin Xu, Xin Gui Fang, Jie Wang & Ming Yao Xu, On cubic s-arc transitive Cayley graphs of finite simple groups, European J. Combin. 26 (2005), 133–143.

[46] Shang Jin Xu, Xin Gui Fang, Jie Wang & Ming Yao Xu, 5-arc transitive cubic Cayley graphs on finite simple groups, European J. Combin. 28 (2007), 1023–1036.

Author’s address: Department of Mathematics, University of Auckland, Private Bag 92019, Auckland, New Zealand

Author’s e-mail address: m.conder@auckland.ac.nz