Also available at http://amc.imfm.si
ISSN 1855-3966 (printed ed.), ISSN 1855-3974 (electronic ed.)
ARS MATHEMATICA CONTEMPORANEA 1 (2008) 144–153
Cayley Graphs, Cori Hypermaps, and Dessins
d’Enfants
David Singerman
School of Mathematics, University of Southampton, Southampton SO17 1BJ,
United Kingdom
Jürgen Wolfart
Mathematisches Seminar, Goethe Universität, Postfach 111932, D-60054 Frankfurt a. M.,
Germany
Received 17 September 2008, accepted 4 November 2008, published online 11 November 2008
Abstract
This paper explains some facts probably known to experts and implicitely contained in
the literature about dessins d’enfants but which seem to be nowhere explicitely stated. The 1-
skeleton of every regular Cori hypermap is the Cayley graph of its automorphism group,
embedded in the underlying orientable surface. Conversely, every Cayley graph of a fi-
nite two-generator group has an embedding as the 1-skeleton of a regular hypermap in the
Cori representation. For non-regular hypermaps there is an analogous correspondence with
Schreier coset diagrams.
Keywords: Cayley graph, dessin d’enfant, hypermap.
Math. Subj. Class.: 20F65, 05C25, 05C65, 30F35
1 Hypermaps and Belyı̆ functions
We recall the definition of hypermaps, more precisely compact, oriented topological hyper-
maps in their Cori representation (see [1], [2], [8]). Let X be a compact orientable surface.
A hypermap H on X is a triple (X,S,A) where S and A denote closed subsets of X with
the following properties.
1. B = S ∩A is a finite set. Its elements are called the brins ofH .
2. S ∪A is connected.
E-mail addresses: D.Singerman@soton.ac.uk (David Singerman), wolfart@math.uni-frankfurt.de (Jürgen
Wolfart)
Copyright c© 2008 DMFA – založništvo
D. Singerman, J. Wolfart: Cayley Graphs, Cori Hypermaps, and Dessins d’Enfants 145
1
2 3
4
5
6
7
8
9
Figure 1: Hypermap on the torus.
3. The components of S — called the hypervertices — and of A — called the hyperedges
ofH— are homeomorphic to closed discs.
4. The components of the complement X\S∪A are homeomorphic to open discs, called
the hyperfaces ofH .
As a very simple example consider Figure 1. Here the shaded triangles are hyperedges and
the black triangles are hypervertices. The white regions are the hyperfaces. This hypermap
lies on the torus obtained by identifying opposite edges of the dotted surrounding hexagon.
Hypermaps were first introduced in [1] as tools for computer science. However, nowa-
days they are a natural ingredient for the dessins d’enfants on smooth projective algebraic
curves over number fields. (Grothendieck called hypermaps dessins d’enfants.) Recall the
definition of a Belyı̆ function β on a compact Riemann surface X as a meromorphic noncon-
stant function ramified at most above {0, 1,∞} , and recall Belyı̆ ’s famous theorem of 1979
that a Belyı̆ function exists on a Riemann surface X if and only if — as an algebraic curve
— X can be defined over a number field, see e.g. [7] or [8]. To every such Belyı̆ function β
we can associate a hypermap H = (X,S,A) in the following way.
On the Riemann sphere C we define a universal target hypermap H0 = (C, S0, A0)
by taking S0 and A0 as closed cells containing 0 and 1 in their respective interiors and in-
tersecting at precisely one point on their boundary. Take e.g. a lemniscate curve around 0
and 1 with node point 12 . This becomes the unique brin, S0 and A0 will be the left and the
right part of the curve with their respective inner points, see Figure 2. For any Belyı̆ function
β : X → C , the closed sets S = β−1(S0) and A = β−1(A0) satisfy the hypermap condi-
tions, the brins are the preimages β−1( 12 ) and represent the sheets of the ramified covering
β . The first proposition is a variant of a well known central fact in the dessin d’enfant theory.
Proposition 1. Every hypermapH = (X,S,A) determines a unique conformal structure on
the compact surface X such that there is a Belyı̆ function β on X with H = β−1H0 .
In the next section we will recall an easy argument for the proof. As explained above,
X has then not only a Riemann surface structure but can be considered even as a smooth
algebraic curve over a number field.
146 Ars Mathematica Contemporanea 1 (2008) 144–153
In the following, we will mainly use the 1-skeleton graph G defined on X by the boundary
of S ∪ A with the brins as vertices. All vertices of G have valency 4 , and the valencies of
the faces reflect ramification properties of the associated Belyı̆ function β.
Proposition 2. Every hypervertex s contains a unique zero of β of order val(s) , every hy-
peredge a contains a unique zero of β − 1 of order val(a) , and every hyperface f contains
a unique pole of β of order 12val(f) .
We mention two other possibilities to represent topological hypermaps:
The Walsh representation [10] as a bipartite graph on X arises from H choosing a white
vertex in the interior of every component of S and a black vertex in the interior of every
component of A , and choosing an edge for every brin b joining the black and the white
vertex in the middle of the components of S and A meeting in b . In the context of Belyı̆
functions, these bipartite graphs arise as β-preimages of a universal target graph, the real
interval [0, 1] with 0 as white and 1 as black vertex, see Figures 3 and 4(b). In this model,
the orders of zero of β and β − 1 are the valencies of the white and the black vertices, and
the pole orders are half of the valency of the faces.
The James representation can be obtained from the Cori representation by blowing up
the components of S and A so that they meet no longer in isolated points but in 1-cells
ending in the common intersection points of hypervertices, hyperedges and the closure of the
hyperfaces. In this model, all vertices of the graph defined by the boundary of S and A have
valency 3 , and moreover this has the advantage that all valencies of faces are twice the order
of zeros of β, β − 1, β−1 respectively, hence reflecting the natural symmetry of the critical
values 0, 1,∞ . A drawing of the example of Figure 1 in the James representation is given in
Figure 4(a). In Figure 4(b) we draw the universal target hypermap.
Note: The Figures 1, 3 and 4(a) are hypermaps for the Fermat cubic x3 + y3 = z3 and
its Belyı̆ function β(x : y : z) := x3/z3 , see Example 3 of Section 7 of [7].
2 The algebraic hypermap
An algebraic hypermap is a quadruple (H,B, g0, g1) consisting of a permutation group H
acting transitively on a finite set B and generated by two elements g0, g1 . The following two
facts are well known by [1] and [2].
Proposition 3. There is a one-to-one correspondence between topological and algebraic
hypermaps.
We sketch one direction of the proof. For a topological hypermapH letB the set of brins,
and note that from every brin b starts a unique edge of the graph G having a component of
0 12 1
S0 A0
Figure 2: A lemniscate curve.
D. Singerman, J. Wolfart: Cayley Graphs, Cori Hypermaps, and Dessins d’Enfants 147
Figure 3: The Walsh representation.
a)
0 1
S0 A0b)
Figure 4: a) Same example as in Figure 1 and 3, but in James representation. b) The universal
target hypermap in James representation.
148 Ars Mathematica Contemporanea 1 (2008) 144–153
S to the left; call its end vertex g0(b) . Similarly, in every b ∈ B starts a unique edge of
G having a component of A to the left; call its end vertex g1(b) . These g0, g1 generate a
permutation group acting on B , the hypercartographic group H . Since G is connected, the
action is transitive.
The other direction of the proof, i.e. the construction of a topological hypermap from an
algebraic one, could be performed in a similar way, but it will be easier using the universal
hypermap; see the end of this section.
Remarks. 1) For the covering defined by the Belyı̆ function, H is the monodromy group.
2) In the Walsh representation, H is a permutation group acting on the set of edges, and
g0, g1 generate the cyclic permutations of the edges around the white resp. black vertices in
counterclockwise order.
3) Similarly, in the James representation we may consider permutations of the set of boundary
edges between S and A . However we will concentrate on the Cori representation for reasons
which will become clear in the next section.
4) According to Proposition 3, we will use the same letterH for both the topological and the
algebraic hypermap.
Definition. A permutation α of B is called an automorphism of the hypermap H =
(H,B, g0, g1) if it is H-equivariant, i.e. if
α(g(b)) = g(α(b)) for all b ∈ B and for all g ∈ H .
A hypermap is called regular if AutH acts transitively on B .
Note that this last condition is equivalent to saying that AutH is of order |B| since
a nontrivial automorphism cannot have fixed points on B . By the transitivity of H , any
automorphism α is uniquely determined by the image of one single brin b . Other ways to
reformulate the regularity condition are given in Theorem 2 of [2]:
Proposition 4. For a hypermapH the following conditions are equivalent.
1. H is regular;
2. AutH is isomorphic to H ;
3. |H| = |B| .
For the consequences of regularity on the associated Belyı̆ functions and the underlying
quasiplatonic curves see [11, Theorems 4 and 5]. We can add a further equivalence taking
into account that H acts transitively and without fixed points on the set of brins.
Proposition 5. The hypermapH is regular if and only if for some brin b ∈ B the mapping
H → B : g 7→ g(b)
is injective, hence defines an identification of H with B . In this case, every b ∈ B defines
such an identification. In this setting, H acts on H = B by left multiplication.
We call H a hypermap of type (p, q, r) if the generators of the hypercartographic group
H are of order
p = ord g0 , q = ord g1 , r = ord g∞ for g∞ := (g0g1)−1 .
D. Singerman, J. Wolfart: Cayley Graphs, Cori Hypermaps, and Dessins d’Enfants 149
For regular hypermaps of type (p, q, r) we can now give the following easy argument to
prove Proposition 1 and to construct a topological hypermap from an algebraic one. Let ∆
be the triangle group of signature (p, q, r) , that is with presentation
< γ0, γ1, γ∞ | γp0 = γ
q
1 = γ
r
∞ = γ0γ1γ∞ = 1 >
acting discontinuously on the simply connected domain U — in the most common case
1
p +
1
q +
1
q < 1 that is the upper half plane equipped with the hyperbolic metric. On U we
can construct a universal Walsh hypermap (see [2]) by taking the fixed point s0 of γ0 and
all its ∆-images as white vertices, taking the ∆-orbit of the fixed point s1 of γ1 as the set
of black vertices, and taking the geodesic path between s0 and s1 and all its ∆-images as
edges. (As an exercise we leave to the reader the question how to modify this construction in
the case U = C where the γi have two fixed points.) Consider the kernel K of the obvious
homomorphism
∆ → H ∼= AutH , γi 7→ gi for i = 0, 1,∞ .
The quotient X := K\U has a unique complex structure, and we find the original hypermap
(in its Walsh representation) as the quotient of the universal hypermap by K . At the same
time, this construction gives the Belyı̆ function forH as quotient map
K\U → ∆\U ∼= C
if we identify the ∆-orbits of the fixed points of γ0, γ1, γ∞ with 0, 1,∞ . Moreover, we see
that AutH ∼= ∆/K acts as a group of holomorphic automorphisms on the Riemann surface
X (caution: this action on the edges or the brins is in general very different from the action
of the isomorphic group H introduced after Proposition 3).
The general case of non-regular hypermaps can be derived from the regular case: Let F
be the subgroup of H fixing the brin b . Then there is a H-equivariant bijection between the
set B of brins and the left cosets hF ∈ H/F . If Γ is the preimage of F under the canonical
group homomorphism ∆ → ∆/K ∼= H used above, the surface X is now the quotient
Γ\U , again having a canonical conformal structure and a canonical Belyı̆ function. We note
in particular
Proposition 6. Every hypermap is isomorphic to the quotient of a regular hypermap by some
subgroup F of its automorphism group. As algebraic hypermaps, the regular hypermap
(H,H, g0, g1) and its quotient (H,H/F, g0, g1)
have the same hypercartographic group and the same generators, acting on H and on H/F
by left multiplication. For the topological hypermaps, the underlying surfaces are X and
F\X where F acts as a subgroup of the automorphism group of X .
3 Cayley graphs
Using Propositions 3 and 5 and an identification B = H of the set of brins with the hyper-
cartographic group we can state now the main result.
Theorem 7. Let H = (X,S,A) = (H,H, g0, g1) be a regular hypermap of type (p, q, r) .
Then the 1-skeleton of the hypermap in its Cori representation is the Cayley graph of H with
generators g0 and g1 .
150 Ars Mathematica Contemporanea 1 (2008) 144–153
1
2 3
4
5
g0
g0 g0
g1
g1g1
Figure 5: An enlargement of part of Figure 1.
Proof. Suppose for simplicity that the orders of the generators are > 2 , the other cases
will be treated separately in Section 5. Proposition 5 gives already a labelling of the brins
(= vertices) with the group elements. It remains to give a direction to the edges and to label
them with the generators g0 or g1 . By construction of the hypercartographic group, every
edge leads from a vertex h to a vertex gi(h) = gi · h , so the label gi and the direction are
obvious. (In other words, in the direction of the edge the complement of S ∪A is at its right,
it has either a component of S or a component of A at its left, and according to these two
cases we have i = 0 or 1 , respectively.) From Figures 1, 3, 4(a) we get Figure 5.
With these labels, G becomes the Cayley graph of H . Note that this Cayley graph is
embedded in X in a special way: the edges incident with any vertex h are g0, g−10 , g1, g
−1
1
in counterclockwise order around h , see Figure 5. Here we assume the obvious convention
to label a gi-edge ending in h locally by g−1i . For example in Figure 5 we get
g0 = (9, 2, 7)(6, 8, 1)(3, 4, 5) , g1 = (2, 3, 1)(4, 6, 7)(8, 9, 5)
and then
g1g0 = (1, 7, 5)(2, 4, 8)(3, 6, 9)
( g0 followed by g1 ).
The group H generated by g0 and g1 is C3 ×C3 and so the graph G can be regarded as a
way of drawing the Cayley graph of C3 × C3 on a torus.
Remark 5) Similarly to the definitions given in Section 1 one may introduce also infinite
hypermaps, e.g. the universal hypermaps used in Section 2, if we omit the compactness of
X and replace finiteness of B with discreteness. Counting arguments do not work anymore,
therefore our version of Proposition 4 does not apply to infinite regular hypermaps, for the-
ory and examples see [6]. However, Proposition 5 remains valid, and therefore Theorem 7
generalises to infinite regular hypermaps as well.
We come back to the finite case and think of H as a permutation group acting on H by
left multiplication. With the same local counterclockwise ordering g0, g−10 , g1, g
−1
1 of the
edges in the Cayley graph as above, we use the direction of Proposition 3 from the algebraic
hypermap (H,H, g0, g1) to the topological hypermap H = (X,S,A) and get the following
converse of Theorem 7.
D. Singerman, J. Wolfart: Cayley Graphs, Cori Hypermaps, and Dessins d’Enfants 151
Theorem 8. Let H be a finite group with two generators g0, g1 . Its Cayley graph G has an
embedding into a compact oriented surface X as the 1-skeleton of a hypermapH in its Cori
representation.
4 Schreier coset diagrams
The generalisation of Theorem 7 to the case of not necessarily regular hypermaps is obvious.
Theorem 9. Let H be a hypermap whose hypercartographic group H is generated by ele-
ments g0, g1 . Then the 1-skeleton graph G of its Cori representation is an embedding of the
Schreier coset diagram of the left residue classes H/F into the surface X where F is the
subgroup of H fixing a brin b ofH .
Note that, according to Proposition 6, we use here the multiplication of H on H/F from
the left, not the convention of [3]. (For the case of generators of order 1 or 2 see again the
next section.) The choice of the brin is irrelevant because H acts transitively on the set of
brins, so all fixing subgroups are conjugate in H and lead to isomorphic Schreier diagrams.
There is also a converse to Theorem 9, but for the precise statement we have to recall that by
construction as a permutation group the hypercartographic group acts effectively on B . In
other words, the trivial subgroup {1} is the only normal subgroup of H contained in F . To
pass from an arbitrary coset diagram to an algebraic hypermap we have therefore to divide
out a certain normal subgroup.
Theorem 10. Let Φ be a finite group with two generators φ0, φ1 and U a subgroup of Φ ,
and let N be the intersection of all subgroups conjugate to U . Suppose that in
H := Φ/N , F := U/N
H has generators gi := φi mod N , i = 0, 1 . Then the Schreier coset diagram of Φ/U is
the 1-skeleton G of the hypermap H = (X,S,A) = (H,H/F, g0, g1) , embedded into the
compact surface X .
5 Remarks about maps and involutions
For the proofs in the last two sections we supposed always the generators to be of order > 2 .
How to modify definitions and proofs in the very common cases where one of the generators
is an involution and the other is of order > 2 ? Usually in the case g21 = 1 hypermaps are
replaced with maps obtained by the Walsh representation of the hypermap — where all black
vertices have valency 2 — simply by omitting these black vertices. Then the action of the
cartographic group H :=< g0, g1 > has to be defined on the set of darts, i.e. on the directed
edges of the resulting graph. But this graph is not the Cayley graph of H , of course.
One possibility to overcome this difficulty is to apply the concept of hypermaps as de-
scribed above literally also to the case of a generating involution g1 , accepting that the com-
ponents of A are only digons whose boundary edges are labelled both with g1 = g−11 . This
leads in Theorems 7 and 8 not to the usual concept of Cayley graphs (see [3]) in which only
one edge for a generator of order 2 starts from every vertex . These usual Cayley graphs are
obtained with another possibility already proposed in [2]: collapse the components of A to
one-dimensional edges, so replace the respective condition 3. in the hypermap definition with
3a. The components of A are homeomorphic to closed intervals.
152 Ars Mathematica Contemporanea 1 (2008) 144–153
0 12 1
S0 A0
Figure 6: Universal target for a modified Cori representation of maps of type (p, 2, r).
See [2], Figure 6, for an example of type (6, 2, 3) . Clearly for the corresponding Belyı̆
functions there is a universal target hypermap of this type pictured in Figure 6. S0 is the left
half of the lemniscate curve together with its interior points, and A0 is the closed interval
between 12 and 1 , the only brin is
1
2 . Note that all brins in the so-defined hypermaps have
valency 3 as vertices in its 1-skeleton graph G . With these conventions, all proofs above
extend without difficulty to the case of order 2 generators.
We leave it to the reader to extend this consideration to the very special situations that
both generators are involutions or one generator is the identity.
Of course, many authors have explored the connections between Cayley or Schreier
graphs and Map Theory. For example A. Vince [9] has constructed Schreier maps from
the Coxeter group that contains the group generated by g0 and g1 with index 2. In our context
this Schreier graph is the 1-skeleton of the James representation of the dessin, see Figure 4
and [5]. The Vince and James approach also applies to non-orientabe hypermaps, see also
Izquierdo and Singerman [4]. However, no one has previously used the Cori representation
or stressed the connection with dessin d’enfants.
Acknowledgements
We would like to thank Martin Fluch for his help with producing the diagrams and Gareth
Jones for hints concerning infinite regular hypermaps.
References
[1] R. Cori, Un code pour les graphes planaires et ses applications, Astérisque 27 (1975).
[2] D. Corn and D. Singerman, Regular hypermaps, European J. Combinatorics 9 (1988), 337–351.
[3] H. S. M. Coxeter and W. O. J. Moser, Generators and Relations for Discrete Groups, Ergebnisse
der Math. 34, Springer, 1965.
[4] M. Izquierdo and D. Singerman, Hypermaps on surfaces with boundary, European J. Combina-
torics 15 (1994), 159–172.
[5] L. D. James, Operations on hypermaps and outer automorphisms, European J. Combinatorics 9
(1988), 551–560.
[6] G. A. Jones, J. M. Jones and J. Wolfart, On the regularity of maps, J. Combin. Theory, Ser. B 98
(2008) 631–636.
[7] G. A. Jones and D. Singerman, Belyı̆ Functions, Hypermaps and Galois Groups, Bull. London
Math. Soc. 28 (1996), 561–590.
D. Singerman, J. Wolfart: Cayley Graphs, Cori Hypermaps, and Dessins d’Enfants 153
[8] D. Singerman, Riemann surfaces, Belyı̆ functions and hypermaps, in: E. Bujalance, A.F. Costa,
E. Martinez (eds.) Topics on Riemann Surfaces and Fuchsian Groups, London Math. Soc. LNS
287, Cambridge UP, 2001, 43–68.
[9] A. Vince, Combinatorial Maps, J. Combinatorial Theory Ser. B 34 (1983), 1–21.
[10] T. R. S. Walsh, Hypermaps versus bipartite maps, J. Combinatorial Theory Ser. B 18 (1975),
155–163.
[11] J. Wolfart, ABC for polynomials, dessins d’enfants, and uniformization — a survey, in: W.
Schwarz, J. Steuding (eds.) Elementare und Analytische Zahlentheorie (Tagungsband), Pro-
ceedings ELAZ–Conference, May 24–28, 2004, Steiner Verlag Stuttgart, 2006, 313–345.
(http://www.math.uni-frankfurt.de/∼wolfart/)