Cayley diagram for A4 |
Permutation diagram for A4 |

Monochrome diagram for A4 |
Dessin d'enfant for A4 |

and discusses the relationships between them. They all show permutation groups, with the set permuted being of vertices, vertices, half-edges and edges respectively.

Two other graphical representations of groups are shown below.
This page does **not** discuss Coxeter or Coxeter-Dynkin diagrams.

Coxeter diagram for BC_{3} |
Coxeter-Dynkin diagram for BC_{3} as full symmetrygroup of the truncated octahedron |

A Cayley diagram, also know as a Cayley graph, is a coloured directed graph, with as many vertices as the group has elements. It is based on a set of generators of the group, with one colour for each generator. Each vertex corresponds to an element of the group, and has one incoming and one outgoing edge of each colour.

A widely-used convention is that, if a generator has order 2, so that the edges of its corresponding colour form pairs like this , each pair of such edges is replaced by a single undirected edge of that colour, .

It may be considered more elegant to draw a Cayley diagram without the edges crossing. The smallest genus of surface in which this is possible is known as the genus of the group.

A Cayley diagram can be drawn for any finite group, given a set of generators. One method is to assign a colour to each generator, draw a vertex that corresponds to the identity element, and start adding edges and more vertices, with each vertex corresponding to an element of the group. However, arranging for the result to look symmetrical may not be trivial.

C7 |
---|

C2×C2×C2 |
---|

C2×C2×C2 |
---|

A4 |
---|

A4 |
---|

The quaternion group |
---|

The quaternion group, in a torus |
---|

The Frobenius group of order 20 |
---|

The Frobenius group of order 20, in a torus |
---|

The Frobenius group of order 42, in a torus |
---|

The order-16 Pauli group |
---|

The order-16 Pauli group, in a genus-2 surface |
---|

S4 in a torus |
---|

S4 |
---|

SL_{2}(3)drawn badly |
---|

SL_{2}(3) |
---|

SL_{2}(3)in a torus |
---|

PSL_{2}(7) in agenus-3 surface |
---|

A permutation diagram shows the structure of a permutation group.

Like a Cayley diagram, it is a coloured directed graph, based on a set of generators (which are here permutations) of the group, with one colour for each generator. Each vertex corresponds to a member of the set that is permuted by the group. As for a Cayley diagram, the edges of any one colour must form a set of closed loops; but unlike a Cayley diagram, there may be vertices which are not on any circuit of some colour.

In these pages, I use two conventions for permutation diagrams. One is that, as for Cayley diagrams, if a generator has order 2, each pair of such edges is replaced by a single undirected edge. The other is that each loop is assumed to run clockwise, unless accompanied by the symbol in the same colour as the loop to indicate that it runs counterclockwise.

A permutation diagram can be drawn for any permutation group.

If a permutation group has *n*-fold rotational symmetry, and there
is an element of the group which corresponds to this symmetry element,
then the element leaves the diagram effectively unchanged, and must
therefore commute with every element of the group. Therefore the group
must have a central subgroup C_{n}. In the examples shown
below, we see that SL_{2}(3) has 2-fold rotational symmetry,
generated by the square of the black generator. Therefore it must have
a central C_{2} subgroup.

In general, a permutation diagram represents a permutation group; the items permuted can be anything. This includes those permutation groups where the items permuted are a subgroup of the group and its cosets.

For any group, we can choose some subgroup, form all its right-cosets, and consider how the subgroup and cosets are permuted by the elements of the group. Then we can draw a permutation diagram for this permutation group. an example follows. If the subgroup we choose is a normal subgroup, we get a permutation diagram for its quotient in the original grooup; otherwise (as in the example below) we get a permutation diagram for the whole group.

Permutation diagram of A4, permuting the cosets of the subgroup ( 1, (abc), (acb) ) |
---|

We start with A4, regarded as permuting the letters
(**a**,**b**,**c**,**d**). We choose a subgroup:
(1,(abc),(acb)). We form its right cosets:

We choose two generators: (ab)(cd) and (abc).

We find how the two generators act on the cosets, and draw the permutation diagram, as shown to the right.

C2×C2 |
---|

C2×C2 |
---|

C4 |
---|

C6 |
---|

C6 |
---|

C30 |
---|

C30 |
---|

D8 |
---|

D8 |
---|

D8 |
---|

D8 |
---|

Q8 |
---|

C4 ⋊ C4 |
---|

A4 |
---|

S4 |
---|

S4 |
---|

S4 |
---|

A5 |
---|

A5 |
---|

A5 |
---|

A5 |
---|

Frob20 |
---|

Frob20 |
---|

Frob21 |
---|

Frob42 |
---|

SL_{3}(2) |
---|

SL_{2}(3) |
---|

PSL_{2}(7) |
---|

PSL_{2}(7) |
---|

PSL_{2}(7) |
---|

AGL_{1}(8) |
---|

AGL_{1}(9) |
---|

M11 |
---|

M12 |
---|

A monochrome diagram is a graph, which may include half-edges connected to only one vertex, embedded in some orientable surface. They are shown here with black vertices, and red edges and half-edges. They are called monochrome because all the vertices are the same colour, unlike the related dessins d'enfants which have both black and white vertices.

Monochrome diagram for PSL _{2}(5) |
---|

A monochrome diagram represents a permutation group with two generators, one of which is of order 2. The elements permuted are its half-edges (counting each full edge as two half-edges). The "red" generator, which must be of order 2, flips each full edge, interchanging the two half-edges which comprise it. The "black" generator cycles all the half-edges connected to each vertex, one place clockwise around that vertex. (Hence the surface in which the graph is embedded must be orientable; "clockwise" is undefined over a non-orientable surface).

The monochrome diagram to the right is for PSL_{2}(5). It acts on six half-edges,
which are marked with the letters (**a**, **b**, **c**, **d**, **e**, **f**).
The "black" generator cycles the half-edges around each vertex, performing the permuattion
(a b d e f)(c), and the "red" generator flips each edge, performing the permutation (b c)(e f).

Thus the embedding, without self-intersection, of any graph into a
surface gives rise to a *cartographic group*^{J01 p.7}.

A4 |
---|

A4×C2 |
---|

A5 |
---|

A5 |
---|

A5 |
---|

A5 |
---|

A5 |
---|

A5 |
---|

A5 |
---|

A5 |
---|

A5 |
---|

A5 |
---|

D6×C3 |
---|

D8 |
---|

Pauli |
---|

Frob20 |
---|

Frob42 |
---|

S6 |
---|

S6≀C2 |
---|

AGL_{1}(8) |
---|

PGL_{2}(3) |
---|

PSL_{2}(5) |
---|

PGL_{2}(7) |
---|

PGL_{2}(11) |
---|

PSL_{2}(13) |
---|

PSL_{2}(17) |
---|

PGL_{2}(19) |
---|

GL_{2}(3) |
---|

GL_{2}(3) |
---|

PSL_{2}(7) |
---|

PSL_{2}(7) |
---|

PSL_{2}(7) |
---|

PSL_{2}(7) |
---|

M11 |
---|

M12 |
---|

A dessin d'enfant is a bipartite graph embedded in some orientable surface in such a way as to partition it into "faces" each having the topology of a disk.

Dessin d'enfant for PSL _{2}(5) |
---|

Dessins d'enfants are normally shown with the vertices shown in black and white, so that each edge connects a black vertex to a white vertex.

It represents a permutation group with two generators. The elements permuted are its edges. The "black" generator cycles all the half-edges connected to each black vertex, one place clockwise around that vertex, and the "white" generator likewise around each white vertex. (Hence, as for monochrome diagrams, the surface must be orientable). An example, with the edges marked with letters, is shown to the right. The "black" generator is (a b d e f)(c), and the "white" generator is (b c)(e f).

The embedding, without self-intersection, of any bipartite graph into a
surface gives rise to a *monodromy group*^{J01 p.2}.

C2×C2 |
---|

D6 |
---|

Frob20 |
---|

Frob21 |
---|

Frob42 |
---|

Q8 |
---|

(C2×C2)⋊C4 |
---|

AGL_{1}(8) |
---|

C3×C3 |
---|

A4 |
---|

A4 |
---|

M12 |
---|

A **Cayley diagram** is a special case of a **permutation diagram**.
Specifically, it is a permutation diagram for which the set of
vertices corresponds to the elements of the group.
It is therefore also a special case of those permutation diagrams
for which the set of vertices corresponds to the set of cosets of
a subgroup of the group: here the subgroup is the trivial group.

A **permutation diagram** can be converted directly to a **monochrome
diagram** iff it

- is connected
- uses no more than two generators
- has no more than one generator of order greater than two

To the right we see a permutation diagram and a monochrome diagram for A4: the red order-2 generator of the former becomes the edges of the latter, and the black generator becomes the vertices.

A **monochrome diagram** can always be converted directly to a
**dessin d'enfant diagram**, by adding a new, white, vertex on
each edge. An example, for the group PSL_{2}(5), is shown
to the right.

A **monochrome diagram** can also be converted to a
**permutation diagram**, which will have two generators
(colours), one corresponding to to the vertices and the other,
of order 2, to the edges.

A **dessin d'enfant** can be converted to a **monochrome diagram**
iff, for either the black or the white vertices, all vertices of that
colour have degree 1 or 2.
A **dessin d'enfant** can always be converted to a **permutation
diagram** with two colours (generators).
If a bipartite graph can be drawn as a **monochrome diagram**
with cartographic group **C**, and as a **dessin d'enfant**
with monodromy group **M**, then we find that **M** is isomorphic
to the wreath product of **C** by the group of order 2.

A **Cayley diagram** is necessarily connected.

C4 ⋊ C4 |

A **permutation diagram** need not be connected. A connected
permutation diagram acts transitively on its vertices, a
disconnected permutation diagam does not. Some groups, such as
C4⋊C4, can usefully be shown by disconnected permutation
diagrams, as seen to the right. The two components of the
example diagram are permutation diagrams for D8 and for C4; but
the red colour common to both links them, so that the diagram
as a whole is not a permutation diagram for D8×C4.

A **monochrome diagram** need not be connected. A connected
monochrome diagram acts transitively on its half-edges, and a
disconnected monochrome diagam does not. The cartographic group
of a disconnected monochrome diagam is the direct product of
the cartographic groups of its connected components. Published
disconnected monochrome diagrams are not often seen.

A **dessin d'enfant** is necessarily connected, as the definition
of "dessin d'enfant" specifies that it must partition its embedding
surface into regions with the topology of a disk.

Cayley diagram for SL _{2}(3),immersed in a plane |
Cayley diagram for SL _{2}(3),embedded in a torus |

**Cayley diagrams** are often drawn with their edges crossing,
as shown in the first diagram to the right. Which of these two
Cayley diagrams one prefers is a matter of aesthetics. The lowest
genus of surface in which a Cayley diagram for a group can be
embedded is known as the "genus" of the group.

**Permutation diagrams** are often drawn with their edges crossing.

**Monochrome diagrams** are not drawn with their edges crossing. They
are shown embedded in surfaces.

**Dessins d'enfants** are not drawn with their edges crossing. They
are shown embedded in surfaces, usually the sphere, or equivalently
the plane.
A function which is the quotient of two polynomials maps the
Riemann sphere
to itself. The mapping is homeomorphic except at a finite number of
"critical points", which form the vertices of a dessin d'enfant.