Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 4 (2011) 313–328
Classification and Galois conjugacy of
Hamming maps
Gareth A. Jones
School of Mathematics, University of Southampton, Southampton SO17 1BJ, UK
Received 10 December 2009, accepted 16 July 2011, published online 20 August 2011
Abstract
We show that for each d ≥ 1 the d-dimensional Hamming graph H(d, q) has an orientably
regular surface embedding if and only if q is a prime power pe. If q > 2 there are up to iso-
morphism φ(q−1)/e such maps, all constructed as Cayley maps for a d-dimensional vector
space over the field Fq . We show that for each such pair (d, q) the corresponding Belyı̆ pairs
are conjugate under the action of the absolute Galois group Gal Q, and we determine their
minimal field of definition. We also classify the orientably regular embeddings of merged
Hamming graphs for q > 3.
Keywords: Hamming graph, Hamming map, automorphism group, Galois group.
Math. Subj. Class.: 20B25; 05C10, 05C25, 14H37, 14H55, 30F10
1 Introduction
A mapM on an oriented surface is said to be orientably regular if its orientation-preserving
automorphism group Aut+M acts transitively on the arcs (directed edges) ofM. A stan-
dard problem in topological graph theory is that of classifying the orientably regular em-
beddings of a given class of arc-transitive graphs. This has been solved for several classes,
for instance complete graphs Kn [2, 13], complete bipartite graphs Kn,n [15], merged
Johnson graphs J(n,m)I [14], n-cubes Qn for n odd [9], and, according to a recent an-
nouncement [5], also Qn for n even. Here we solve this problem for the d-dimensional
Hamming graphs H(d, q), where q > 2. (When q = 2 we have H(d, 2) ∼= Qd with a
completely different classification.) There are, up to isomorphism, φ(q − 1)/e orientably
regular embeddings when q = pe for some prime p, and none otherwise. As in the case
d = 1, when H(1, q) ∼= Kq , these maps are all Cayley maps for a d-dimensional vector
space over the field Fq of q elements. By contrast, Kwon [23] has recently classified the
non-orientable regular embeddings of Hamming graphs, and in addition to the well-known
E-mail address: G.A.Jones@maths.soton.ac.uk (Gareth A. Jones)
Copyright c© 2011 DMFA Slovenije
314 Ars Math. Contemp. 4 (2011) 313–328
non-orientable embeddings of H(1, 6) = K6 of type {3, 5} and {5, 5}, obtained as antipo-
dal quotients of the icosahedron and great dodecahedron [12], there are two non-orientable
embeddings of H(2, 6) of type {8, 10} and {10, 10}; see [16] for their classification and
construction.
We also consider the distance k Hamming graphs H(d, q)k and the merged Hamming
graphs H(d, q)K , ∅ 6= K ⊆ D = {1, 2, . . . , d}: we show that if such a graph has an
orientably regular embedding then q is a prime power, and if q ≥ 4 then the only ori-
entably regular embeddings are those of H(d, q)1 = H(d, q) described above, and the
Biggs maps [2] for the complete graph H(d, q)D = Kqd . The method of proof depends
on a classification of the mergings of the Hamming association scheme by Muzychuk [25],
which applies only for q ≥ 4; the case q = 3 remains open.
According to Grothendieck’s theory of dessins d’enfants [10, 18], maps on compact
oriented surfaces correspond to algebraic curves defined over the field Q of algebraic num-
bers. Here we apply some general methods recently developed by Streit, Wolfart and the
author [21], based on Wilson’s map operations [28], to show that for q > 2 the orientably
regular embeddings of each H(d, q) form an orbit under the absolute Galois group Gal Q,
and that their minimal field of definition is the splitting field of p in the cyclotomic field of
the (q − 1)-th roots of 1. In particular, they are defined over Q if and only if q ≤ 4.
The author is grateful to Jürgen Wolfart, and to the Mathematics Institute of the J. W.
Goethe University, Frankfurt-am-Main, for hospitably arranging and funding a visit during
which much of this research was carried out, and also to him and to Mikhail Klin and
Manfred Streit for their helpful comments on early drafts of this paper. He also thanks the
organisers of GEMS 09 for their invitation to announce these results at Tále, Slovakia.
2 Construction of Hamming maps
The d-dimensional Hamming graph H = H(d, q) has vertex set V = Qd where Q is a set
of q elements (q ≥ 2), with vertices v = (vi) and w = (wi) adjacent if and only if vi = wi
for all except one value of i. Each vertex thus has valency
n = d(q − 1).
In any connected graph, the distance between two vertices v and w is defined to be the
minimum number of edges in any path from v to w; in this case it coincides with the
Hamming distance, the number of i such that vi 6= wi. The automorphism group A =
A(d, q) of H is the wreath product Sq o Sd of the symmetric groups Sq and Sd. This is a
semidirect product B :Sd of a normal subgroup B = B1 × · · · × Bd, with the i-th direct
factor Bi ∼= Sq acting naturally on i-th coordinates vi ∈ Q and fixing j-th coordinates
vj for j 6= i, by a complement Sd which permutes the coordinates v1, . . . , vd of each
v ∈ V . If we take Q to be a group, then V is also a group, and H is its Cayley graph with
respect to the generating set S consisting of the elements of V with exactly one non-identity
coordinate.
In certain cases one can form an orientably regular map which embedsH in an oriented
surface. Let q be a prime power, and let Q be the field F = Fq of q elements, so that the
vertex set V of H is a d-dimensional vector space over F , and S consists of the non-
zero multiples of the standard basis vectors e1, . . . , ed of V . Let ω be a generator of the
multiplicative group F ∗ = F \{0} ∼= Cq−1 of F , and let M = Mω be the d×d monomial
matrix over F with non-zero entries mi,i+1 = 1 for i = 1, . . . , d− 1 and md,1 = ω. Then
G. A. Jones: Classification and Galois conjugacy of Hamming maps 315
Md = ωI , soM induces an invertible linear transformation of V of order n, permuting the
elements of S in a single cycle. This cyclic ordering
e1, e1M = e2, . . . , e1M
d−1 = ed, e1M
d = ωe1, . . . , e1M
d(q−1)−1 = ωq−2ed (2.1)
of S determines a Cayley map H = H(d, ω) for H: the cyclic order of the neighbours of
any vertex v, induced by the local orientation around v, is obtained by adding each vector
in (2.1) to v. This map, which we will call a Hamming map, is orientably regular since
M induces an automorphism of the group V (see [27, Theorem 16-27]). The orientation-
preserving automorphism group G = Aut+H(d, ω) ofH is a semidirect product V :G0 of
an elementary abelian normal subgroup V ∼= F d ∼= (Cp)de, acting regularly by translations
on the vertices, by a complement G0 ∼= Cn fixing the vertex 0 = (0, . . . , 0); a generator of
G0 permutes the neighbours of 0 in a single cycle, given by (2.1).
These Hamming maps are generalisations of the orientably regular embeddingsH(1, ω)
of the complete graphs Kq ∼= H(1, q) introduced by Biggs in [2]. James and the author
showed in [13] that the maps H(1, ω) are the only orientably regular embeddings of com-
plete graphs, and here (for q > 2) we extend this result to all dimensions d ≥ 1:
Theorem 2.1. LetM be an orientably regular embedding of the d-dimensional Hamming
graph H(d, q). Then q is a prime power, and if q > 2 thenM is isomorphic to a Hamming
mapH(d, ω) where ω is a generator of the multiplicative group F ∗q .
The proof, given in §6, uses finite group theory, including basic properties of Frobenius
groups, though it is independent of the classification of finite simple groups. This result
has been obtained independently by Kwon [22] for odd q, using a different method which
represents oriented maps as pairs of permutations. The condition q > 2 is necessary here,
at least for d ≥ 3, since in this case there are more orientably regular embeddings of
the d-dimensional hypercube Qd ∼= H(d, 2) than the single Hamming map H(d, ω), with
ω = 1 ∈ F2: for instance if d is odd then as shown by Du, Kwak and Nedela [9] there
are, up to isomorphism, 2r orientably regular embeddings of Qd, where r is the number
of distinct primes dividing d. The freedom to create additional embeddings when q = 2
seems to depend on H(d, 2) being bipartite, which is not the case for H(d, q) when q > 2.
For any prime power q the number of distinct Hamming maps H(d, ω) is φ(q − 1),
the number of generators ω of F ∗q , where φ is Euler’s function. If ω
′ = ωγ for some
field automorphism γ of Fq , then letting γ act naturally on V induces an isomorphism
H(d, ω) → H(d, ω′). Our second main theorem, proved in §7 and also generalising a
result for d = 1 in [13], shows that these are the only cases in whichH(d, ω) ∼= H(d, ω′):
Theorem 2.2. Let ω and ω′ be generators of the multiplicative group of the field Fq . Then
H(d, ω) ∼= H(d, ω′) if and only if ω and ω′ are conjugate under the Galois group of Fq .
If q = pe for some prime p then the Galois group GalFq is cyclic of order e, generated
by the Frobenius automorphism t 7→ tp. Since this group acts fixed-point-freely on the
generators of F ∗q , we have the following immediate corollary to Theorems 2.1 and 2.2:
Corollary 2.3. If q = pe > 2 for some prime p then there are, up to isomorphism, exactly
φ(q − 1)/e orientably regular embeddings of H(d, q) for each d ≥ 1.
It is, perhaps, a little surprising that this number is independent of the dimension d. Like
Corollary 2.3, the following result, proved in §3, generalises one proved for d = 1 in [13].
An orientably regular mapM is reflexible if it has an orientation-reversing automorphism.
316 Ars Math. Contemp. 4 (2011) 313–328
Corollary 2.4. For each d ≥ 1, the only reflexible Hamming maps are the unique Hamming
maps for q = 2, 3 or 4. In particular, the only reflexible embeddings of H(d, q) for q > 2
are the Hamming maps with q = 3 or 4.
3 Properties of Hamming maps
In any orientably regular mapM, the faces have the same valency m, the vertices have the
same valency n, and the Petrie polygons (closed zig-zag paths) have the same length l. We
then say thatM has type {m,n}l, or simply {m,n}. We now compute the type of the map
H(d, ω).
Lemma 3.1. LetM be a Cayley map for an abelian group A, in which the cyclic order of
the generators is given by successive iterates αi(s) of an automorphism α of A applied to
an element s ∈ A. Then
(a) if the automorphism −α : a 7→ −α(a) of A fixes only 0 in A then the face valency
m is the order of this automorphism;
(b) the Petrie length l is twice the order of the element (α− 1)(s) = α(s)− s in A.
Proof. By its construction,M is orientably regular (see [27, Theorem 16-27]), so all faces
have the same valency m. Successive vertices around one particular face are
s, 0, α(s), α(s)− α2(s), α(s)− α2(s) + α3(s), . . .
so m is the least j > 0 such that
α(s)− α2(s) + α3(s)− · · · − (−1)jαj(s) = 0. (3.1)
If (3.1) holds, then applying α−1 and adding, we see that (−α)j(s) = s; since the au-
tomorphism −α commutes with α this implies that (−α)j(αi(s)) = αi(s) for all i, so
(−α)j = 1 since the elements αi(s) generate A. Conversely, if (−α)j = 1 then
(α−1 + 1)(α(s)− α2(s) + α3(s)− · · · − (−1)jαj(s)) = s− (−1)jαj(s) = 0,
so α−1, and hence also α, inverts the left-hand side of (3.1). It follows that if α inverts only
0 ∈ A then (3.1) holds, so m is the order of −α.
Similarly all Petrie polygons in M have the same length l. A typical Petrie polygon
has successive vertices
s, 0, α(s), α(s)− s, 2α(s)− s, 2α(s)− 2s, . . . , jα(s)− (j − 1)s, jα(s)− js, . . . ,
so l is twice the order of (α− 1)(s). 
The vertices of the Hamming mapH(d, ω) have valency n = d(q−1), and Lemma 3.1
(b) shows that the Petrie length is l = 2p, where q = pe and p is prime.
Lemma 3.1(a) applies to the Hamming maps H(d, ω) for q > 3, and also for q = 3 if
d is even: since the matrix M = Mω has characteristic polynomial λd − ω we see that −1
cannot be an eigenvalue in these cases. Now (−M)d = (−1)dωI , and this is ωI if q or d
is even, giving m = n; if q and d are both odd then (−M)d = −ωI with ω(q−1)/2 = −1,
so m = n or n/2 as q ≡ 1 or −1 mod (4). Thus m = n in all these cases except when d is
odd and q ≡ −1 mod (4), in which case m = n/2.
G. A. Jones: Classification and Galois conjugacy of Hamming maps 317
To deal with the exceptional cases, first let q = 3 with d odd. Then ω = −1 so
Md = −I and hence (−M)d = I; directly calculating the left-hand side of (3.1) shows
that m = 3d. Finally, if q = 2 then ω = 1, and this time calculating the left-hand side
of (3.1) gives m = 2d. To summarise, m = n unless
• d is odd and 3 < q ≡ −1 mod (4), in which case m = n/2, or
• d is odd and q = 3, in which case m = 3d, or
• q = 2, in which case m = 2d.
Knowing its type, we can now compute the Euler characteristic and hence the genus of
H(d, ω). The numbers of vertices, edges and faces are qd, d(q−1)qd/2 and d(q−1)qd/m
respectively. It follows that if m = d(q − 1) thenH(d, ω) has characteristic
χ = 2qd − d(q − 1)q
d
2
=
qd
2
(
4− d(q − 1)
)
and hence genus
g = 1 +
qd
4
(
d(q − 1)− 4
)
.
If 3 < q ≡ −1 mod (4) and d is odd then m = d(q − 1)/2, soH(d, ω) has characteristic
χ = 3qd − d(q − 1)q
d
2
=
qd
2
(
6− d(q − 1)
)
and hence genus
g = 1 +
qd
4
(
d(q − 1)− 6
)
.
If q = 3 and d is odd then m = 3d, so
χ = 3d − 3dd+ 2.3d−1 = 3d−1(5− 3d)
giving
g = 1 +
3d−1(3d− 5)
2
.
If q = 2 then m = 2d, so
χ = 2d − 2d−1d+ 2d−1 = 2d−1(3− d)
and hence
g = 1 + 2d−2(d− 3).
We now consider the effect of Wilson’s operationsHj , which act on maps by preserving
the graph and raising the cyclic order of neighbours of each vertex to its j-th power, where
j is coprime to the valency [28].
Lemma 3.2. Hj(H(d, ω)) ∼= H(d, ωj) for all j coprime to d(q − 1).
Proof. By raising the cyclic order of neighbours of 0 to its j-th power we do the same to the
induced d-cycle on the coordinate places, resulting in another d-cycle since j is coprime to
d, and we replace ω with ωj , which is a generator of F ∗q since j is coprime to q − 1. This
gives the required isomorphism. 
318 Ars Math. Contemp. 4 (2011) 313–328
Corollary 3.3. The mirror image ofH(d, ω) is isomorphic toH(d, ω−1). 
If q = 2 or 3 then ω = ±1, so this implies that H(d, ω) is reflexible; the same applies
when q = 4 since ω−1 = ω2 is conjugate to ω under the Galois group of F4 (see §2).
If q ≥ 5 then ω−1 and ω are never conjugate, so in this case Theorem 2.2 implies that
H(d, ω) and its mirror image are non-isomorphic, forming a chiral pair. This, together
with Theorem 2.1, proves Corollary 2.4.
Lemma 3.4. For a given pair d and q, the automorphism groups of the Hamming maps
H(d, ω) are mutually isomorphic.
Proof. Let H(d, ω) and H(d, ω′) be Hamming maps for a given pair d and q. Their auto-
morphism groups G and G′ are semidirect products of V = F dq by Cn, with a generator
of Cn acting linearly on V as the matrix Mω or Mω′ with respect to the standard basis
e1, . . . , ed. We have ω′ = ωj for some j coprime to q − 1, and we can choose j also
to be coprime to d. Then M jω acts linearly on V as the matrix Mω′ with respect to the
basis e1, e1M jω, e1M
2j
ω , . . . , e1M
(d−1)j
ω , so applying the appropriate change-of-basis au-
tomorphism of V and raising the elements of G0 to their j-th powers gives the required
isomorphism G→ G′. 
We will denote this common automorphism group by G = G(d, q).
4 Examples
(a) First we will briefly describe the mapsH(d, ω) of genus g up to 101, to allow compari-
son with Conder’s classification [6] of orientably regular maps in the range 2 ≤ g ≤ 101;
the cases g = 0 and 1 are well-known, and can be found in [8]. We exclude the Ham-
ming maps with d = 1 since these are the well-known complete maps discovered by
Biggs [2, 13]. In most cases, a few numerical parameters such as the genus, type (including
Petrie length), and number of automorphisms are sufficient to identify the map in Conder’s
lists, but occasionally one also needs to use the presentations of the automorphism groups
in [6]. These examples are presented in increasing order of d.
If q = 2 the unique Hamming map H(2, ω) has type {4, 2}4 and genus 0 with |G| = 8;
this is the reflexible map {4, 2} in [8, Ch. 8], the spherical embedding of a cycle of length
4.
If q = 3 the unique Hamming map H(2, ω) has type {4, 4}6 and genus 1 with |G| = 36;
this is the reflexible map {4, 4}3,0 in [8, Ch. 8], also a Paley map [27, §16.8] for the Paley
graph P9.
If q = 4 the unique Hamming map H(2, ω) has type {6, 6}4 and genus 9 with |G| = 96;
this is the self-dual map R9.18 in Conder’s list of reflexible maps [6].
If q = 5 the two Hamming mapsH(2, ω) have type {8, 8}10 and genus 26 with |G| = 200;
these form the chiral pair C26.1 in Conder’s list of chiral maps [6].
If q = 7 the two Hamming maps H(2, ω) have type {12, 12}14 and genus 99 with |G| =
588; these form the chiral pair C99.2 in [6].
If q = 2 the unique Hamming map H(3, ω) has type {6, 3}4 and genus 1 with |G| = 24;
this is the reflexible map {6, 3}2,0 in [8, Ch. 8], the Petrie dual of the cube {4, 3}.
If q = 3 the unique Hamming mapH(3, ω) has type {9, 6}6 and genus 19 with |G| = 162;
this is the dual of the reflexible map R19.15 in [6].
G. A. Jones: Classification and Galois conjugacy of Hamming maps 319
If q = 4 the unique Hamming mapH(3, ω) has type {9, 9}4 and genus 81 with |G| = 576;
this is the self-dual reflexible map R81.125 in [6].
If q = 2 the unique Hamming map H(4, ω) has type {8, 4}4 and genus 5 with |G| = 64;
this map, an embedding of the hypercube Q4, is the dual of the reflexible map R5.5 in [6].
If q = 3 the unique Hamming mapH(4, ω) has type {8, 8}6 and genus 82 with |G| = 648;
this is the self-dual reflexible map R82.50 in [6].
If q = 2 the unique Hamming mapH(5, ω) has type {10, 5}4 and genus 17 with |G| = 160;
this map, an embedding of Q5, is the dual of the reflexible map R17.18 in [6].
If q = 2 the unique Hamming mapH(6, ω) has type {12, 6}4 and genus 49 with |G| = 384;
this map, an embedding of Q6, is the dual of the reflexible map R49.39 in [6].
(b) To see a class of examples for which there is more than one chiral pair of embed-
dings, let q = 25. For each d ≥ 1 there are φ(24)/2 = 4 non-isomorphic Hamming
maps H(d, ω). For instance, the embeddings H(1, ω) of the complete graph K25 consid-
ered in [13, §8] have type {24, 24}10 and genus 126, while the maps H(2, ω) have type
{48, 48}10 and genus 6876. For each d these four maps correspond to the four orbits of
GalF25 ∼= C2 on the φ(24) = 8 generators of F ∗25, or equivalently to the four irreducible
quadratic factors t2±t+2 and t2±2t−2 of the cyclotomic polynomial Φ24(t) = t8−t4+1
over F5, each arising as the minimal polynomial of a conjugate pair of generators. The
maps form two chiral pairs, each pair corresponding to a mutually inverse pair of genera-
tors of F ∗25, and transposed with the other pair by Wilson’s operation H7.
5 Preliminaries for the classification
For each i = 1, . . . , d let∼i be the equivalence relation on the vertex set V ofH = H(d, q)
defined by v ∼i w if and only if vi = wi, and let πi be the corresponding partition of V ,
consisting of q equivalence classes [v]i of size qd−1. The automorphism groupA = AutH
permutes these d partitions πi, acting as the symmetric group Sd; the kernel of its action
is the normal subgroup B = B1 × · · · × Bd of A, with Bi acting faithfully as Sq on the q
classes in πi, while the other factors Bj leave each of these classes invariant.
For each i = 1, . . . , d let ≈i be the conjunction (or intersection) of the equivalence
relations ∼j for j 6= i; this is the equivalence relation on V defined by v ≈i w if and only
if vj = wj for all j 6= i. The corresponding partition Πi of V consists of qd−1 equivalence
classes [[v]]i of size q. Again, A permutes these d partitions Πi as Sd, with kernel B, but
in this case Bi is the kernel of the action of B on the classes in Πi.
Each class [[v]]i in Πi is a maximal clique (complete subgraph) in H . For each k =
0, . . . , d let Hk(v) denote the set of vertices at distance k from v. Then the set H1(v) of
neighbours of v inH is the disjoint union of the cliques [[v]]∗i = [[v]]i\{v} for i = 1, . . . , d.
(This fact easily implies the well-known result that AutH ∼= Sq o Sd.)
In order to prove Theorem 2.1 we need the following result:
Lemma 5.1. The automorphisms of a Hamming graph H fixing a vertex v are represented
faithfully on H1(v).
Proof. Suppose that a graph automorphism g fixes v and all its neighbours. For k ≥ 2,
each vertex in Hk(v) is uniquely determined by its k neighbours in Hk−1(v), so it follows
by induction on k that g fixes every vertex of H . 
320 Ars Math. Contemp. 4 (2011) 313–328
6 Proof of Theorem 2.1
Let G = Aut+M for some orientably regular embeddingM of H(d, q), where q > 2. As
explained earlier, it is shown in [13] that Theorem 2.1 is true for d = 1, so we may assume
that d ≥ 2.
The subgroupGv ofG stabilising a vertex v ∈ V is a cyclic group of order n = d(q−1),
acting regularly on the set H1(v) of neighbours of v. Since G ≤ A, Gv acts imprimitively
on H1(v), permuting the d cliques [[v]]∗i transitively. Let K = G ∩ B, the kernel of the
action of G on the d partitions Πi of V . Then Kv = Gv ∩ K is a cyclic group of order
q−1 acting regularly on each of the d sets [[v]]∗i . It follows from Lemma 5.1 that Kvw = 1
for each w ∈ V \ {v}. This will show that K acts on V as a Frobenius group, provided we
can show that K acts transitively but not regularly on V . If w ≈i v then Kw acts regularly
on [[w]]∗i = [[v]]i \ {w}. The subsets [[v]]∗i and [[w]]∗i of [[v]]i = [[w]]i have non-empty
intersection since q > 2, so all elements of [[v]]i are in the same orbit of K. Since the
transitive closure of the d equivalence relations ≈i is the universal relation, K is transitive
on V , and since |Kv| = q − 1 > 1 it follows that K acts as a Frobenius group on V .
As a Frobenius group, K has a normal subgroup N acting regularly on V , namely the
Frobenius kernel [11, V.7.6, V.8.2]. Since N is a Hall subgroup of K, it is a characteristic
subgroup of K [11, V.8.3] and hence it is normal in G. It follows that G is a semidirect
product of N by Gv for each v ∈ V .
Let us choose a particular element of Q, denoted by 0Q, and let 0 denote the vertex
(0Q, . . . , 0Q) ∈ V . We can identify V with N so that 0 is the identity element, N acts on
V by right multiplication, and G0 acts on V by conjugation. For each i the equivalence
class [[0]]i containing 0 is identified with a subgroupNi of order q, namely the subgroup of
N preserving [[0]]i. Since K0 acts transitively by conjugation on the non-identity elements
of Ni, this subgroup is elementary abelian, so q = pe for some prime p. This proves the
first part of Theorem 2.1.
In order to prove the second part, we first need to show thatN induces a regular permu-
tation group on the set of q classes in each partition πi. There is a simple proof of this when
q is odd, using the fact that the order q − 1 of the Frobenius complement K0 is then even,
so that the Frobenius kernel N is abelian [11, V.8.18(a)]. This argument fails, however,
when q = 2e, so instead we give an alternative argument which applies in all cases.
For each i, K permutes the q classes in the partition πi as a transitive permutation
group K(i). The subgroup K0 preserves the class [0]i, and permutes the other q− 1 classes
regularly, soK(i) is a 2-transitive group. The normal subgroupN ofK has order qd = pde,
so it induces a normal p-group N (i) ≤ K(i), and this contains the regular subgroup N (i)i
induced by the subgroupNi on πi. IfN (i) > N
(i)
i then the stabiliser of [0]i inK
(i) contains
a non-trivial normal p-subgroup; the orbits of this subgroup on the remaining q− 1 classes
must have the same length l > 1 dividing q− 1, which is impossible since q− 1 is coprime
to p. Thus N (i) = N (i)i , so N induces a regular permutation group N
(i) on πi. Each
subgroup Nj (j 6= i) of N sends 0 to elements of [[0]]j ⊆ [0]i, so it preserves the class
[0]i and is therefore contained in the kernel of this action of N on πi. This is true for all
i 6= j, so Nj is contained in the kernel N ∩ Bj of the action of N on Πj . Thus Nj ≤ Bj
for each j, so the subgroups N1, . . . , Nd generate their direct product N1× · · ·×Nd in N ,
and comparing orders we see that N = N1 × · · · ×Nd. Thus N is an elementary abelian
p-group of rank de.
Let x be the standard generator of G0, permuting the edges ofM incident with 0 by
G. A. Jones: Classification and Galois conjugacy of Hamming maps 321
following the local orientation around this vertex. Then x permutes the sets [[0]]∗i in a cycle
of length d, and by renumbering if necessary (equivalently, by applying an automorphism
of H) we may assume that it acts on the subscripts i as the cycle (1, 2, . . . , d).
The subgroup K0 = 〈xd〉 of K, being cyclic and acting transitively on the non-identity
elements of eachNi ∼= (Cp)d, must act on eachNi as a Singer cycle [11, II.3.10, II.7.3], so
in particular one can identify N1 with the field F = Fq so that xd acts on N1 as multiplica-
tion by a generator ω of F ∗. By composing this identification F → N1 with the bijection
N1 → Ni induced by xi−1 for each i = 2, . . . , d, we get an identification F → Ni of
Ni with F so that xd also acts on Ni as multiplication by ω. Then x : Ni → Ni+1 acts
as the identity on F for i = 1, . . . , d − 1, while x : Nd → N1 acts as multiplication by
ω. By Lemma 5.1 this action of x on N1 ∪ · · · ∪ Nd has a unique extension to a graph
automorphism of H , namely the cyclic permutation defined in (2.1) of §2. This shows that
the vertex-set V = N can be regarded as the d-dimensional vector space F d over F , with
x acting as the matrix Mω with respect to the standard basis, soM∼= H(d, ω). 
7 Proof of Theorem 2.2
We need to show that if H(d, ω) ∼= H(d, ω′) where ω and ω′ are generators of F ∗, then ω
and ω′ are in the same orbit of GalF . Equivalently, we need to show that a Hamming map
M determines ω uniquely, up to automorphisms of F .
Given such a map M, let us choose a pair of adjacent vertices, and label them with
the elements 0 and e1 of V . (The particular choice is immaterial, since M is orientably
regular.) In the proof of Theorem 2.1, the unique maximal clique [[0]]1 of H containing 0
and e1 is identified with the 1-dimensional subspace N1 of N = V = F d spanned by e1;
we can therefore identify it with the field F = Fq , by identifying each element λe1 (λ ∈ F )
of [[0]]1 with λ. We need to find this identification explicitly, in order to determine ω.
By following the orientation of M around 0 we obtain the neighbours of 0 in the
cyclic order given by (2.1); the d-th power of this cyclic permutation, starting with the
chosen vertex e1, therefore identifies the elements of [[0]]∗1 with the successive powers
1, ω, ω2, . . . , ωq−2 of ω. This gives us a cyclic group structure on [[0]]∗1, which we can
regard as the multiplicative group F ∗ of F .
In order to determine the additive structure of [[0]]1 it is sufficient to find the difference
of each distinct pair of elements v = ωi and w = ωj of [[0]]∗1, expressing v−w as a power
of ω. In the cyclic order of the neighbours of w in M, the vertex 0 = w + (−w) must
be followed, dk terms later for some integer k, by the vertex v, so that v = w + ωk(−w).
Thus v − w = ωk(−w), and this is either ωj+k or ωj+k+(q−1)/2 as q is even or odd,
since −1 = ω(q−1)/2 in the latter case. This shows thatM uniquely determines the field
structure of F , so it determines the minimal polynomial of ω over the prime field Fp, and
hence it determines ω up to an automorphism of F . 
8 Characterisation by valency and automorphisms
For future applications, we need to show that the Hamming mapsH(d, ω) are characterised
among all orientably regular maps by their valency and their orientation-preserving auto-
morphism group. We first summarise some basic general facts about orientably regular
maps; for background, see [17], for instance.
For any group G, the orientably regular mapsM with Aut+M∼= G correspond to the
generating pairs x, y for G such that y has order 2. Here x is a rotation fixing a vertex v of
322 Ars Math. Contemp. 4 (2011) 313–328
M, sending each incident edge to the next incident edge according to the local orientation
around v, while y is a half-turn, reversing one of these incident edges, so that z = (xy)−1
is a rotation preserving an incident face. We will call x and y standard generators of G.
Conversely, given generators x and y of a groupGwith y2 = 1 one can construct a mapM,
with arcs corresponding to the elements of G, and vertices, edges and faces corresponding
to the cosets inG of the cyclic subgroups generated by x, y and z; this map has type {m,n}
where m and n are the orders of z and x. Two such maps are isomorphic if and only if the
corresponding pairs of standard generators are equivalent under AutG.
We will apply this theory to the common automorphism group G = G(d, q) of the
Hamming maps for H(d, q), described in §3.
Lemma 8.1. If q > 2 then the matrix Mω satisfies
n−1∑
i=0
M iω = 0.
Proof. By direct calculation, each entry of the matrix
∑n−1
i=0 M
i
ω is equal to µ =
∑q−2
i=0 ω
i.
Since ωq−1 = 1 we have ωµ = µ, and hence µ = 0 since ω 6= 1 when q > 2. 
[If q = 2 then
∑n−1
i=0 M
i
ω is the d× d matrix J with all entries equal to 1.]
Each element of the semidirect productG = V :G0 has a unique factorisation vg where
v ∈ V and g ∈ G0. We will use this to determine the elements of order n and 2 in G.
Corollary 8.2. An element vg ∈ G, with v ∈ V and g ∈ G0, has order n if and only if g
has order n.
Proof. For each k ≥ 1 we have
(vg)k = (gk)(g−kvgk)(gk−1vgk−1) . . . (g−1vg).
If g has order n then putting k = n and using the fact that the successive powers of g act
on V as the powers of Mω in some order, we see from Lemma 8.1 that (vg)n = 1, so vg
has order dividing n. Since vg maps onto the element g of order n under the epimorphism
G→ G/V ∼= G0, it has order exactly n.
Conversely, suppose that vg has order n, so g has order k dividing n. If k < n then 1 6=
(vg)k = g−kvgk.gk−1vgk−1. . . . .g−1vg ∈ V , so (vg)k has order p and hence k = n/p.
Thus g is a primitive power of xp. Since p divides n = d(q − 1) with q = pe we see that
p divides d. However, a simple calculation, along the lines of Lemma 8.1, then shows that∑k−1
i=0 M
pi
ω = 0 and hence (vg)
k = 1, a contradiction. Thus g has order n. 
If d is even or q is odd, then the order n = d(q − 1) of the cyclic group G0 is even, so
there is a unique involution g2 ∈ G0.
Corollary 8.3. If q is odd then the elements of order 2 inG are those of the form vg2 where
v ∈ V . If q is even then the elements of order 2 in G are the elements of V \ {1}, and also,
if d = 2c is even, those of the form vg2 where v = (vi) ∈ V with vi+c =
√
ωvi for each
i = 1, . . . , c. 
The proof, which we omit, is similar to that for Corollary 8.2. When q and d are even,
the elements v ∈ V such that vi+c =
√
ωvi are the fixed points of g2 in V , forming an
FqG-submodule U of V of dimension c = d/2.
G. A. Jones: Classification and Galois conjugacy of Hamming maps 323
IfM∼= H(d, ω) then the standard generators x and y have orders n and 2, and generate
G = Aut+M∼= G(d, q). The following result shows that the converse is also true.
Proposition 8.4. If elements x and y of orders n and 2 generate G = G(d, q), then the
corresponding orientably regular map is isomorphic to a Hamming mapH(d, ω) for some
generator ω of F ∗q .
Proof. First suppose that q is odd. It follows from Corollaries 8.2 and 8.3 that if x and y
have orders n and 2 then xn/2 and y are both elements of V g2, so y = wxn/2 for some
w ∈ V and hence 〈x, y〉 = 〈w, x〉. Let X = 〈x〉 and let W be the normal closure of w
in V , that is, the cyclic FpG-submodule of V generated by w. Then 〈w, x〉 = W :X , so
W = V since w and x generate G = V :X . Thus V is generated by w as an FpG-module.
Now V has the structure of a vector space over Fq , with G acting linearly on V , so V is
also generated by w as an FqG-module. Since G acts on V as the cyclic group G/V , with
the subgroup of index d inducing scalar transformations, the 1-dimensional Fq-subspace
spanned by w has at most d distinct images in V , namely the 1-dimensional subspaces
Wi spanned by wx
i
for i = 0, . . . , d − 1. In order for the d-dimensional space V to be
spanned by w as an FqG-module, these d subspaces Wi must be distinct and V must be
their direct sum; these subspaces are cyclically permuted byX , with xd acting on V as ωId
for some generator ω of F ∗q . In the orientably regular mapM with standard generators x
and y forG, each vertex is identified with a coset gX ofX inG, and hence with the unique
element v ∈ V ∩ gX . Since y ∈ wX , one of the neighbours of the vertex 0 is w, and so
the neighbours of 0 are the conjugates of w in G. These are the non-zero elements of the
subspaces Wi, with their cyclic ordering given by iteration of Mω , soM∼= H(d, ω).
Now suppose that q is even, so that the second part of Corollary 8.3 applies to y. If
y ∈ V we define w = y, and then the proof proceeds as before. The other possibility is that
d is even and y ∈ V g2. But then xn/2 and y are both involutions not contained in V , so
they are both elements of Ug2, where U is the subgroup of V fixed by g2. Thus y = wxn/2
as before, but with w contained in the proper FqG-submodule U of V . It follows that
〈x, y〉 = 〈w, x〉 ≤ U :X < G, against our hypothesis that x and y generate G. This case
therefore cannot arise. 
9 Galois conjugacy
Grothendieck’s theory of dessins d’enfants [10, 18] shows that a map M on a compact
oriented surface corresponds naturally to a Belyı̆ pair (X,β), where X is a nonsingular
projective algebraic curve over C, and β is a rational function from X to the complex
projective line (or Riemann sphere) P1(C) = C ∪ {∞}, unramified outside {0, 1,∞}.
One can regard X as a Riemann surface underlying M, with the inverse image under β
of the unit interval providing the embedded graph. By Belyı̆’s Theorem [1], X and β are
defined (by polynomials and rational functions) over the field Q of algebraic numbers, and
conversely every curve defined over Q is obtained in this way from a map. Grothendieck
observed that the action of the absolute Galois group Γ = Gal Q on the coefficients of
these functions induces a faithful action of Γ on the associated maps. It is therefore of
interest to determine the orbits of Γ on maps.
The following result extends examples given by Streit, Wolfart and the author in [21];
in particular it generalises the corresponding result [21, Theorem 4] for complete graphs
H(1, q) = Kq:
324 Ars Math. Contemp. 4 (2011) 313–328
Theorem 9.1. For any d ≥ 1 and prime power q = pe, the φ(q − 1)/e Hamming maps
H(d, ω) form an orbit under Γ.
Proof. As shown by Streit and the author [20], various properties of a mapM are invari-
ant under the action of Γ: these include orientable regularity, the (orientation-preserving)
automorphism group Aut+M, and the type {m,n} ofM. Proposition 8.4 shows that for
any given d and q the Hamming maps H(d, ω) are characterised among all orientably reg-
ular maps by their common automorphism group G(d, q) and their valency n = d(q − 1),
so this set of maps is invariant under Γ. Lemma 3.2 shows that these maps form a single
orbit under Wilson’s operations Hj . Now Streit, Wolfart and the author have shown in [21,
Theorem 2] that any set of maps satisfying these two conditions forms an orbit of Γ, so in
particular this applies to the Hamming mapsH(d, ω). 
Theorem 2 of [21] also allows one to determine the minimal field of definition of the
Belyı̆ pairs corresponding to these maps. For any integer m ≥ 1 let ζm = exp(2πi/m) ∈
C. The multiplicative group Z∗m of units mod (m) can be identified with the Galois group
of the cyclotomic field Q(ζm) by identifying each j ∈ Z∗m with the automorphism defined
by ζm 7→ ζjm. It follows from [21, Theorem 2] that the Belyı̆ pairs corresponding to the
maps H(d, ω) are all defined over a particular subfield of Q(ζn), namely the fixed field
K of the subgroup H of Gal Q(ζn) consisting of all j ∈ Z∗n such that Hj(H(d, ω)) ∼=
H(d, ω) for some (and hence every) ω. By Theorem 2.2 and Lemma 3.2, H is the inverse
image of the subgroup 〈p〉 ≤ Z∗q−1 under the natural epimorphism Z∗n → Z∗q−1. This is
a subgroup of index φ(q − 1)/e in Z∗n, containing the kernel of this epimorphism, so K
is an extension of Q of degree φ(q − 1)/e, contained in Q(ζq−1), namely the subfield of
Q(ζq−1) fixed by its automorphism ζq−1 7→ ζpq−1. Equivalently, K is the splitting field of
p in Q(ζq−1), the maximal subfield of Q(ζq−1) in which p decomposes into φ(q − 1)/e
different prime ideals of degree 1 over p.
Example 1. The Belyı̆ pair corresponding to H(d, ω) is defined over Q if and only if
φ(q − 1)/e = 1, that is, q = 2, 3 or 4. As a simple example, the unique orientably
regular embedding of H(2, 2) ∼= Q2 ∼= K2,2 corresponds to the Fermat curve X of genus
0 given (as a projective curve) by x2 + y2 = z2, with Belyı̆ function β : [x, y, z] 7→
4x2(z2−x2)/z4. The vertices are the points [0,±1, 1] and [±1, 0, 1] where β = 0, and the
edges are the points where 0 ≤ β ≤ 1, with their centres at the points [±1/
√
2,±1/
√
2, 1]
where β = 1.
Example 2. If q = 25 then for each d ≥ 1 there are four maps H(d, ω), described in
§4(b). The corresponding Belyı̆ pairs are defined over the splitting field K of the prime
p = 5 in the cyclotomic field Q(ζ24). This is an extension of Q of degree 4, with the
four maps forming an orbit under GalK (a Klein four-group generated by ζ24 7→ ζ−124
and ζ24 7→ ζ724), and hence also forming an orbit under Γ, which acts as GalK via the
epimorphism Γ→ GalK induced by the inclusion of K in Q.
In general, finding explicit equations for a Belyı̆ pair, as in Example 1, is much harder
than finding its Galois orbit or minimal field of definition. It would be interesting to achieve
this for some more of the Hamming maps.
10 Distance k Hamming graphs
The distance k Hamming graphs Hk = H(d, q)k, for k = 1, 2, . . . , d, are generalisations
of the Hamming graphs H = H(d, q). They have the same vertex set V = Qd as H , with
G. A. Jones: Classification and Galois conjugacy of Hamming maps 325
vertices v = (vi) and w = (wi) adjacent in Hk if and only if they are at distance k in H ,
that is, vi 6= wi for exactly k values of i. Thus H1 = H . The vertices of Hk all have
valency
(
d
k
)
(q − 1)k. These graphs are arc-transitive, since A = AutH = Sq o Sd is a
group of automorphisms of Hk, acting transitively on its arcs.
For any subset K of D := {1, 2, . . . , d} let HK = H(d, q)K be the merged Hamming
graph ∪k∈KH(d, q)k: this has vertex set V , with v and w adjacent if and only if they are at
Hamming distance k for some k ∈ K. We have A ≤ AutH(d, q)K for each K, and when
q > 3 we can determine whether these two groups are equal. (We will explain later why
the case q = 3 is excluded here.) Let D0 and D1 denote the sets of even and odd elements
of D.
Proposition 10.1. Let q ≥ 4 and let K be a non-empty subset of D = {1, 2, . . . , d}. Then
AutH(d, q)K = A in all cases except the following:
(a) K = D;
(b) q = 4, d ≥ 3 and K = D0 or D1.
Proof. As the automorphism group of a graph, A is a 2-closed permutation group, that is, it
is the full automorphism group of the set of binary relations on V which it preserves. Any
permutation groupA∗ on V , which properly containsA, must therefore have rank less than
the rank d + 1 of A, so the association scheme A∗ corresponding to A∗ must be a proper
subscheme of the Hamming association schemeA corresponding to A, which has the adja-
cency matrices Ak of the graphs Hk (k = 0, . . . , d) as its basis elements. Muzychuk [25]
has shown that for q ≥ 4 the only such subschemes are the rank 2 association scheme with
basis {A0 = I, A1 + A2 + · · · + Ad}, and the rank 3 association scheme for q = 4 and
d ≥ 3 with basis {A0 = I, A1 + A3 + · · · , A2 + A4 + · · · }. If AutH(d, q)K 6= A then
by applying this to A∗ = AutH(d, q)K we see that K is as described in (a) or (b). 
For q ≥ 5, the fact that AutH(d, q)K = A can also be deduced from the maximality
of the group A = Sq o Sd in the alternating or symmetric group on V : there are proofs
of this by Neumann in [19] and by Liebeck, Praeger and Saxl in [24], both depending on
the classification of finite simple groups, and there is a more elementary proof, valid for
q sufficiently large as a function of d, by Soomro and the author in [19]. Muzychuk’s
classification of subschemes of the Hamming schemes for q ≥ 4 is purely combinatorial,
and is also independent of the classification of finite simple groups.
In the exceptional cases in Proposition 10.1, if K = D then HK is a complete graph
and so its automorphism group is the symmetric group Sqd . If q = 4 then the two comple-
mentary graphsHK corresponding toK = D0 andD1 have the same rank 3 automorphism
group. This can be explained as follows.
Let ω ∈ F4 \ F2. Given any v = (vi) ∈ V = F d4 , one can write each vi uniquely as
xi + ωyi with xi, yi ∈ F2, thus identifying V with F 2d2 . Now x2i + xiyi + y2i = 0 or 1 as
vi = 0 or vi 6= 0, so the subgroup A0 = S3 o Sd of A fixing 0, acting on V as GL2(2) o Sd,
preserves the quadratic form
Q(v) =
d∑
i=1
(x2i + xiyi + y
2
i ),
and is therefore a subgroup of the orthogonal group corresponding to Q. This is the group
GOε2d(2) in ATLAS notation [7], where the sign ε is + or− asQ has Witt index d or d−1,
326 Ars Math. Contemp. 4 (2011) 313–328
that is, as d is even or odd. It follows that the semidirect product A∗ = V :GOε2d(2), with
GOε2d(2) acting naturally on V , is a subgroup of the affine group AGL2d(2) containing
A = V : A0. Now GOε2d(2) has two orbits Γ0 and Γ1 on V \ {0}, consisting of the
isotropic and non-isotropic vectors, those v 6= 0 with Q(v) = 0 or 1, so A∗ acts on V
as a rank 3 group. For K = D0 or D1, the complementary graphs HK on V are defined
by v being adjacent to w if and only if v − w has even or odd Hamming weight (distance
from 0), that is, v − w ∈ Γ0 or Γ1 respectively. These relations are invariant under V and
GOε2d(2), so in each case AutHK contains A
∗ and therefore has rank 3.
Theorem 10.2. Let q ≥ 4 and let K be a non-empty subset of D = {1, 2, . . . , d}. Then
the graph HK = H(d, q)K has an orientably regular embedding if and only if q is a prime
power and K = {1} or D.
Proof. Let q be a prime power. If K = {1} then HK = H and so the existence of an
orientably regular embedding follows from Theorem 2.1. IfK = D thenHK is a complete
graph, and the number qd of vertices is a prime power, so the embeddings constructed by
Biggs [2] give the result.
For the converse, suppose thatM is an orientably regular embedding of HK , and let
G = Aut+M. Then AutHK has a cyclic subgroup G0 fixing 0 and acting regularly on
its neighbours, that is, on the vectors of weight k ∈ K. First suppose that K is not one
of the exceptional subsets in Proposition 10.1, so that AutHK = AutH = A. Then
G0 ≤ A0, so G0 preserves the weights of all vectors and hence K is a singleton {k} for
some k ∈ D. Since G0 acts transitively on the vectors of weight k it must map onto a
subgroup of A/B ∼= Sd acting transitively on the k-element subsets of D; since G0 is
abelian, this subgroup acts regularly on D and hence k = 1, d− 1 or d.
If k = 1 then HK = H , so Theorem 2.1 implies that q is a prime power.
Next suppose that k = d− 1. Then G0, a cyclic group of order d(q− 1)d−1, must map
onto a cyclic subgroup of Sd acting regularly on D. The kernel G0 ∩B, a cyclic subgroup
of B0 = Sdq−1 of order (q − 1)d−1, must map onto a transitive and hence regular subgroup
of each factor Sq−1. The unique subgroup of index q − 1 in G0 ∩ B must therefore be
trivial, so d = 2 and hence k = 1, a case we have already dealt with.
Now let k = d, so G0 is a cyclic subgroup of A0 = Sq−1 o Sd, acting regularly on the
set of vectors of weight d. Since q ≥ 4, A0 acts primitively on this set. Since A0 has a
cyclic regular subgroup, and the degree (q − 1)d is not prime, a theorem of Burnside [4,
§252] and Schur [26] implies that A0 must act doubly transitively, whereas in fact it has
rank d+ 1 > 2. Thus there are no orientably regular embeddings in this case.
Now suppose that K is one of the exceptional sets in Proposition 10.1, so that we have
AutHK > A. If K = D then HK is a complete graph on qd vertices. As shown by
Biggs [2], if this has an orientably regular embedding then qd is a prime power, and hence
so is q. We may therefore assume that q = 4, d ≥ 3 and D = Di for i = 0 or 1. By
the comments following Proposition 10.1, AutHK contains the group A∗ = V :GOε2d(2).
Now A∗0 = GO
ε
2d(2) acts primitively on each of its orbits Γ0 and Γ1 in V \ {0}, and G0
induces a cyclic permutation on the set Γi of neighbours of 0 in HK . It follows from the
theorem of Burnside and Schur mentioned above that (AutHK)0, which contains both of
these groups and does not act as a subgroup of AGL1(p) for any prime p, must act as a
doubly transitive group on Γi. However, this is impossible, since in either graph HK it is
easy to find pairs of neighbours of 0 which are and are not adjacent. 
If q = 3 then the preceding arguments in the case AutHK = A yield one further
G. A. Jones: Classification and Galois conjugacy of Hamming maps 327
example with an orientably regular embedding, namely H(2, 3)2. Once again, K must be
a singleton {k}, with k = 1, d−1 or d, and the first two cases give the same conclusions as
before. In the case k = d, however,A0 = Sq−1 oSd is now imprimitive on vectors of weight
d, so the preceding argument does not apply. Instead, note that a cyclic regular subgroup
G0 of order 2d in A0 would map onto a cyclic group of order 2d−1 in Sd, impossible for
d > 2 since a generator would have to contain a cycle of length 2d−1 > d. Hence d = 2,
so HK = H(2, 3)2, which is isomorphic to H(2, 3) and therefore has a unique orientably
regular embedding. To deal with cases where AutHK > A one would need to know
the subschemes of the Hamming scheme for q = 3. One of these arises from a rank 4
group A∗ = V :GOd(3) ≥ A, where the orthogonal group preserves the quadratic form∑d
i=1 v
2
i , which takes the value 0, 1 or 2 as v has weight congruent to 0, 1 or 2 mod (3).
However, at present there is no complete analogue for q = 3 of Muzychuk’s classification
of subschemes of the Hamming scheme for q ≥ 4. It is hoped to consider this problem in
a future paper.
References
[1] G. V. Belyı̆, On Galois extensions of a maximal cyclotomic field, Math. USSR Izvestija 14
(1980), 247–256.
[2] N. L. Biggs, Automorphisms of imbedded graphs, J. Combin. Theory Ser. B 11 (1971), 132–
138.
[3] N. L. Biggs and A. T. White, Permutation Groups and Combinatorial Structures, London
Math. Soc. Lecture Note Ser. 33, Cambridge Univ. Press, Cambridge, 1979.
[4] W. Burnside, Theory of Groups of Finite Order, 2nd ed., Cambridge University Press, 1911.
[5] D. A. Catalano, M. D. E. Conder, S-F. Du, Y. S. Kwon, R. Nedela and S. E. Wilson, Classifica-
tion of regular embeddings of n-dimensional cubes, J. Alg. Combin. 32 (2010), 215–238.
[6] M. D. E. Conder, Regular maps and hypermaps of Euler characteristic -1 to -200, J. Com-
bin. Theory Ser. B 99 (2009), 455–459, associated lists of computational data available at
http://www.math.auckland.ac.nz/˜conder/hypermaps.html.
[7] J. H. Conway, R. T. Curtis, S. P. Norton, R. A. Parker and R. A. Wilson, ATLAS of Finite
Groups, Clarendon Press, Oxford, 1985.
[8] H. S. M. Coxeter and W. O. J. Moser, Generators and Relations for Discrete Groups (4th ed.),
Springer-Verlag, Berlin-Heidelberg-New York, 1980.
[9] S-F. Du, J. H. Kwak and R. Nedela, Classification of regular embeddings of hypercubes of odd
dimension, Discrete Math. 307 (2007), 119–124.
[10] A. Grothendieck, Esquisse d’un Programme, pp. 5–84 in Geometric Galois Actions 1.
Around Grothendieck’s Esquisse d’un Programme, ed. P. Lochak and L. Schneps, London
Math. Soc. Lecture Note Ser. 242, Cambridge University Press, Cambridge, 1997.
[11] B. Huppert, Endliche Gruppen I, 2nd ed., Springer-Verlag, Berlin - Heidelberg - New York,
1979.
[12] L. D. James, Imbeddings of the complete graph, Ars Combinatoria 16-B (1983), 57–72.
[13] L. D. James and G. A. Jones, Regular orientable imbeddings of complete graphs, J. Com-
bin. Theory Ser. B 39 (1985), 353–367.
[14] G. A. Jones, Automorphisms and regular embeddings of merged Johnson graphs, European J.
Combin. 26 (2005), 417–435.
328 Ars Math. Contemp. 4 (2011) 313–328
[15] G. A. Jones, Regular embeddings of complete bipartite graphs: classification and enumeration,
Proc. London Math. Soc. (3) 101 (2010), 427–453.
[16] G. A. Jones and Y. S. Kwon, Classification of nonorientable regular embeddings of Hamming
graphs, arXiv.math:CO/1107.3187 (2011).
[17] G. A. Jones and D. Singerman, Theory of maps on orientable surfaces, Proc. London Math. Soc.
37 (1978), 273–307.
[18] G. A. Jones and D. Singerman, Belyı̆ functions, hypermaps and Galois groups, Bull. London
Math. Soc. 28 (1996), 561–590.
[19] G. A. Jones and K. D. Soomro, The maximality of certain wreath products in alternating and
symmetric groups, Quart. J. Math. 37 (1986), 419–435.
[20] G. A. Jones and M. Streit, Galois groups, monodromy groups and cartographic groups, pp. 25–
65 in Geometric Galois Actions 2. The Inverse Galois Problem, Moduli Spaces and Mapping
Class Groups, ed. P. Lochak, L. Schneps, London Math. Soc. Lecture Note Ser. 243, Cambridge
University Press, 1997.
[21] G. A. Jones, M. Streit and J. Wolfart, Wilson’s map operations on regular dessins and cyclo-
tomic fields of definition, Proc. London Math. Soc. 100 (2009), 510–532
[22] Y. S. Kwon, private communication, 27 April 2009.
[23] Y. S. Kwon, private communication, 2 July 2009.
[24] M. W. Liebeck, C. E. Praeger and J. Saxl, A classification of the maximal subgroups of the
finite alternating and symmetric groups, J. Algebra 111 (1987), 365–383.
[25] M. E. Muzychuk, Subschemes of Hamming association schemes H(n, q), q ≥ 4, Acta Ap-
plic. Math. 29 (1992), 119–128.
[26] I. Schur, Zur Theorie der einfach transitiven Permutationsgruppen. S. B. Preuss. Akad. Wiss.,
Phys.-Math. Kl. (1933), 598–623.
[27] A. T. White, Graphs of Groups on Surfaces, North-Holland Math. Studies 188, Elsevier, Ams-
terdam, 2001.
[28] S. E. Wilson, Operators over regular maps, Pacific J. Math. 81 (1979), 559–568.