Graphical Representations of Groups

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

Cayley diagram for A4	Permutation diagram for A4
Monochrome diagram for A4	Dessin d'enfant for A4

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

Coxeter diagram for BC₃	Coxeter-Dynkin diagram for BC₃ as full symmetry group of the truncated octahedron

Cayley diagrams: show

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.

Some examples of Cayley diagrams: show


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₂(3) drawn badly


SL₂(3)


SL₂(3) in a torus


PSL₂(7) in a genus-3 surface

Permutation diagrams: show

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₂(3) has 2-fold rotational symmetry, generated by the square of the black generator. Therefore it must have a central C₂ subgroup.

A special class of permutation diagram

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) )

Example

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: (((ab)(cd),(bdc),(adc)), ((bcd),(ac)(bd),(adb)), ((acd),(abd),(ad)(bc))).

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.

Some examples of permutation diagrams: show


C2×C2


C2×C2


C4


C6


C6


C30


C30


D8


D8


D8


D8


Q8


A4


S4


S4


S4


A5


A5


A5


A5


Frob20


Frob20


Frob21


Frob42


SL₃(2)


SL₂(3)


PSL₂(7)


PSL₂(7)

Monochrome diagrams: show

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₂(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).

Example

The monochrome diagram to the right is for PSL₂(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}.

Some examples of monochrome diagrams: show

Dessins d'enfants: show

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₂(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}.

Some examples of dessins d'enfants: show

Comparison of these four types of diagram: show

How they relate to one another

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₂(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.

Must they be connected?

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.

Can their edges cross one another?

Cayley diagram for SL₂(3), immersed in a plane	Cayley diagram for SL₂(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.

Graphical Representations of Groups

Cayley diagrams: show

Some examples of Cayley diagrams: show