Chapter 1
Transitive groups

1.1  Permutation groups

This section is a summary of what you already know about transitive permutation groups.

If W is a set then the set of all permutations of W is a group under the usual product of permutations. It is called the symmetric group on W, and is denoted by Sym W. If w Î W and p Î Sym W, then the image of w under p is denoted by w^p. Our convention is that permutations act from the right; that is the action of the product p₁p₂ of two permutations is defined as w^(p₁p₂) = (w^p₁)^p₂. The symmetric group on the set {1,¼,n} will be denoted by S_n.

Exercise 1 List all elements of S₃ and write out a multiplication table. What is the order of S_n?

Exercise 2 Express each of the following elements of S₈ as a product of disjoint cyclic permutations.

1. 
   

   æ ç è 1 2 3 4 5 6 7 8 7 6 4 1 8 2 3 5 ö ÷ ø ;

2. (4,5,6,8)(1,2,4,5);
3. (6,2,4)(2,5,3)(8,7,6)(4,5);

If i ¹ j then the 2-cycle (i,j) is called a transposition . Every permutation p can be written as a product of transpositions. This decomposition may not be unique, but the number of these transpositions is either always even or always odd - depending on p. A permutation is called even if it is a product of even number of transpositions; otherwise it is odd . The set of even permutations is a subgroup of S_n, which is called the alternating group and denoted by A_n.

Exercise 3 What is the order of A_n? Write the permutations in Exercise 1.2 as a product of transpositions. Which, if any, of these permutations belong to A₈?

1.2  Group actions

Let W be a non-empty set and G a group. We say that G acts on W if for any pair (w,g), such that w Î W and g Î G we have defined an element w^g Î W, such that

(i) w¹ = w for all w Î W;
(ii) (w^g₁)^g₂ = w^(g₁g₂) for all w Î W and g₁, g₂ Î G.

In other words, an action is a function from the Cartesian product W×G to W which satisfies the conditions corresponding to (i)-(ii) above.

Exercise 4 Prove that for every element g Î G the map [`g]:w®w<sup>g</sup> is a permutation of W. Prove that the map g®[`g] is a homomorphism from G to Sym W. Conversely, every homomorphism j:G® Sym W gives rise to an action of G on W. Indeed, show that if g Î G and w Î W, then the assignment (w,g)® w^j(g) defines an action.

According to the previous exercise an action can be viewed as a homomorphism j:G®Sym W. If g Î G, then the image of g under this homomorphism will be denoted by [`g]. Similarly, [`G] denotes the image of G. Note that [`g] Î Sym W, and [`G] £ Sym W.

We will use the following concepts associated with an action. The degree of an action is the size of W. The kernel of an action is the kernel of the associated map j. In other words, the kernel of the action is the set

{g Î G | wg = w for allw Î W}.

It is easy to see that the kernel is a normal subgroup of G. An action is called faithful if its kernel is the trivial subgroup of G.

Suppose that G acts on a set W and w Î W. The set of images of w under G is called the orbit of w and denoted by w^G. That is,

wG = {wg | g Î G}.

Exercise 5 Prove that the set of orbits forms a partition of W.

The stabiliser G_w of the point w is defined as the set of all elements of G that fix w. That is

Gw = {g Î G | wg = w}.

Exercise 6 Prove that G_w is a subgroup of G.

For the following exercise recall the concept of conjugation in a group.

Exercise 7 Let G act on a set W, and let w₁, w₂ be elements of W belonging to the same G-orbit. Prove that G_w2 = (G_w1)^g for any g Î G, such that w₁^g = w₂. Deduce that the stabilisers of the elements of an orbit form a single conjugacy class in G. Deduce that if G is abelian, then G_w1 fixes all elements of the orbit of w₁.

Exercise 8 Suppose that G acts on W and let w₁, w₂ Î W, such that w₁ and w₂ are in the same G-orbit. Then prove that the set

{g Î G | w1g = w2}

is a right coset of G_w1 in G. Prove that there is a one-to-one correspondence between the elements of w₁^G and the set of right cosets of G_w1.

The following theorem is an easy consequence of the previous exercise.

Theorem 9 [The Orbit-Stabiliser Property] The size of the orbit of w is the index of G_w in G. In symbols: |w^G| = |G:G_w|.

Exercise 10 Prove the previous theorem. Deduce that the size of an orbit divides the order of G.

An action is called transitive if G has a single orbit on W; that is w^G = W for all w Î W. It is a consequence of the Orbit-Stabiliser Property that if G acts transitively on W then |W| = |G:G_w| for all w Î W. An action is semi-regular if G_w = 1 for all w Î W. An action is regular if it is transitive and semi-regular. It is easy to see that of G acts regularly on W, then |G| = |W|.

Exercise 11 Let G be an abelian group acting faithfully and transitively on a set W. Prove that G is regular.

Exercise 12 Prove that the following examples all define actions of a group on a set. Decide whether these examples are transitive and compute the kernel for each example.

(i) If G is a permutation group on a set W then G has a natural action on W. Under this action the pair (w,g) is mapped to w^g.
(ii)

The group (Z,+) acts on the real line R by translation. Under this action (r,z)® r+z for all z Î Z and r Î R.
(iii) Let V be a vector space and G the general linear group GL(V). Show that for v Î V and g Î G the assignment (v,g)®v·g defines an action of G on V.
(iv) Let V and G be as in the previous example, and set P to be the set of 1-dimensional subspaces in V. Then show that for p Î P and g Î G, the assignment (p,g)® p^g, where p^g = {v^g | v Î p}, defines an action of G on P.
(v) Let G be any group and let us denote the underlying set of G by the same symbol. Then the group G has an action of the set G defined by (g₁,g₂)®g₁^g₂ = g₂^-1g₁g₂. This action is referred to as the conjugation action of G on itself.

Example 13 [Coset action] A very important example is the so-called coset-action. Let G be any group and H a subgroup of G. The symbol [G:H] denotes the set of right cosets of H in G. Then G acts on [G:H] via the assignment (Hx,g)® H(xg).

Exercise 14 Prove that that this indeed defines an action of G on [G:H]. Could you construct a similar action on the set of left cosets of H?

Exercise 15 If G is a group and H a subgroup then the core of H in G is defined as the largest normal subgroup of G contained in H. It is denoted by Core_G(H). Prove that

(i) Core_G(H) = Ç_{g Î G}H^g;
(ii) Core_G(H) is the kernel of the coset action of G on [G:H].

An important action of every group G is its right-regular representation . Let G be a group and let us denote its underlying set by the same symbol. Then the assignment (g₁,g₂)®g₁g₂ defines an action. In other words the set element g₁ is mapped to the set element g₁g₂ by the group element g₂.

Exercise 16 Prove that the right-regular representation defines a faithful action of G on its underlying set. Can you construct the left-regular representation?

Using the right-regular representation, we can define an injective homomorphism from G to Sym G, where g Î G is mapped to [`g] Î Sym G, where [`g] denotes the image of g under the right-regular representation. The image of the group G under this homomorphism is denoted by [`G]. Note that G can be any abstract group, however [`G] is always a permutation group. As this homomorphism is injective, that is its kernel is trivial, we have G @ [`G]. This proves the following theorem.

Theorem 17 [Cayley] Every group is isomorphic to a permutation group.

Exercise 18 Compute the right regular representation for the following groups: Z₄, S₃, D₈.

1.3  Symmetric graphs

A di-graph or directed graph G is a pair G = (V,E) where V is a non-empty set, whose elements are called vertices, and E is a (possibly empty) subset of V×V, whose elements are called arcs . If (a,b) is an arc of a di-graph then we say that this arc connects the vertices a and b. Such vertices are also called adjacent . A di-graph G = (V,E) is called a simple graph, or briefly a graph if

(i) (a,b) Î E if and only if (b,a) Î E for all a, b Î V; and
(i) (a,a) Ï E for all a Î V.

In other words, a graph is a di-graph whose arcs go in both directions and connect different vertices. If (a,b) is an arc the graph G, then so is (b,a) and these two arcs form an edge of G. Thus an edge of a graph can be viewed as a two element subset {a,b}. If G = (V,E) is a graph then E denotes the set of edges.

A path in a di-graph is a (t+1)-tuple of vertices (a₀,a₁,¼,a_t), such that for all i Î {1,¼,t} either (a_i-1,a_i) or (a_i,a_i-1) is an arc. A di-graph is said to be connected if each pair of vertices is joined by a path.

Let G₁ = (V₁,E₁) and G₂ = (V₂,E₂) be two di-graphs and j:V₁® V₂ a bijection, such that for all a, b Î V₁ we have that (a,b) Î E₁ if and only if (j(a),j(b)) Î E₂. Then j is called an isomorphism between the di-graphs G₁ and G₂ and these two di-graphs are said to be isomorphic. In this case we write G₁ @ G₂. Isomorphic di-graphs can be obtained from each other by relabelling the vertices. Therefore we view isomorphic di-graphs as essentially the same.

Exercise 19 Decide whether the two graphs on Figure 1.19 are isomorphic ornot. If they are then find an isomorphism.

If G = (V,E) is a di-graph then an isomorphism V® V is called an automorphism of G. Thus an automorphism is a bijection V® V, and recall that such a bijection is called a permutation of V. For example the permutation (1,3) is an automorphism of G₁. This can be easily verified by listing all arcs of G₁ and checking that the image of the arc under the permutation (1,3) is also an arc:

(1p,1p) = (3,3) is an arc, (1p,2p) = (3,2) is an arc, (3p,2p) = (1,2) is an arc, (3p,3p) = (1,1) is an arc.

Similarly, the permutation (1,2,3,4) is an automorphism of the graph G₂.

Exercise 21 Check the last statement.

The reason why we can use group theory in the study of di-graphs is the following easy result.

Lemma 22 The set of automorphisms of a given di-graph G = (V,E) is a subgroup of Sym V.

PROOF. Recall that in order to show that the set of automorphisms is a subgroup we have to show that the following hold.

(i) The identity element of Sym V is an automorphism.
(ii) The product of two automorphisms is also an automorphism.
(iii) The inverse of an automorphism is also an automorphism.

The details are left as an exercise. ^[¯]

The automorphism group of a di-graph G is denoted by Aut(G).

Exercise 23 Compute the automorphism groups of the two di-graphs on Figure 1.3 and of the graph on Figure 1.19.

Example 24 Let n ³ 3 and define the circulant graph G with degree n as follows. Let the vertex set of G be {a₁,¼,a_n} and the edge set be

{{a1,a2},{a2,a3},¼,{an-1,an},{an,a1}}.

For instance, the second graph on Figure 1.3 is a circular graph with degree 4.It is easy to see that the automorphism group of G is the dihedral group of order 2n.

If Aut(G) is transitive on the set of vertices then G is said to be a vertex-transitive di-graph.

Exercise 25 Let G = (V,E) be a di-graph. The prove that Aut(G) acts on the set of arcs via the assignment (a,b)^g = (a^g,b^g) for g Î Aut(G) and (a,b) Î E. Show that if G is a graph then Aut(G) has a similar action on the set of edges.

According to the previous exercise, Aut(G) permutes the set of arcs or edges. If Aut(G) is transitive on the set of edges or arcs then G is said to be edge-transitive or arc-transitive, respectively. It is easy to see that the di-graph G₁ does not show any of these properties. On the other hand, G₂ is vertex-transitive, edge-transitive and arc-transitive.

Exercise 26 Show that G₂ is vertex-transitive, edge-transitive, and arc-transitive.

In a di-graph G = (V,E) we use the following notation. If a Î V then set

G(a) = {b Î V | (a,b) Î E}   and G*(a) = {b Î V | (b,a) Î E}.

The numbers |G(a)| and |G^*(a)| are called the out-valency and the in-valency of a, respectively.

Exercise 27 Let G = (V,E) be a di-graph and G £ Aut(G).

(i) If a Î V, then show that G_a acts on G(a) and on G^*(a).
(ii) If a, b Î V and g Î Aut(G), such that a^g = b, then show that G(a)^g = G(b) and G^*(a)^g = G^*(b).

The previous exercise shows that in vertex-transitive di-graphs each vertex has the same in-valency; and each vertex has the same out-valency. This way we can talk about the in-valency and the out-valency of the whole graph. If a is a vertex of a graph G = (V,E), then the number |{b | {a,b} Î E}| is called the valency of a. It is similarly easy to show that if G is a vertex-transitive graph, then the valency of a is independent of a and is an invariant of G. This invariant is called the valency of the graph.

Lemma 28 Let G be a di-graph and G £ Aut(G) a vertex-transitive group of automorphisms. Then G is arc-transitive if and only if G_a is transitive on G(a).

PROOF. Suppose first that G is arc-transitive. If b₁, b₂ Î G(a) then (a,b₁), (a,b₂) Î E, and there is some g Î G, such that (a,b₁)^g = (a,b₂). That is, g Î G_a, and b₁^g = b₂. This shows that G_a is transitive on G(a).

Let us now prove that other direction. Suppose that G_a is transitive on G_a for some a Î V, and let (a₁,b₁), (a₂,b₂) Î E. Then there are some g₁, g₂ Î G, such that a₁^g₁ = a and a₂^g₂ = a. Then (a₁,b₁)^g₁ = (a,b₁^g₁) Î E and (a₂,b₂)^g₂ = (a,b₂^g₂) Î E, and hence b₁^g₁, b₂^g₂ Î G(a). As G_a is transitive on G(a) we have that there is some h Î G_a, such that b₁^g₁h = b₂^g₂. Then

(a1b1)g1hg2-1 = (a,b1g1)hg2-1 = (a,b2g2)g2-1 = (a2,b2).

This shows that G is arc-transitive, as required. ^[¯]

A graph is called bipartite if its vertex set can be partitioned into two parts so that each edge has exactly one vertex in each part. A bipartite graph is often drawn so that the vertices are drawn in two columns, according to the bipartition. In this graphical representation there is no edge between vertices belonging to the same column. The graph on Figure 1.19 isbipartite (in fact there are two graphs on the picture, but, as they are isomorphic, one is bipartite if and only if the other).

Theorem 29 If a connected graph is edge-transitive, but not vertex-transitive, then it is bipartite.

PROOF. Suppose that G = (V,E) is a connected, edge-transitive, but not vertex-transitive graph. Let {x,y} be an edge of G and let X and Y denote the orbits of x and y, respectively, under the action of Aut(G). As X and Y are orbits, they are either disjoint or identical. Since G is connected, every vertex z is in some edge {z,w}. As Aut(G) is edge-transitive, there is an element g Î Aut(G), such that {z,w}^g = {x,y}, and hence z^g is x or y. Thus Aut(G) has at most two orbits on V. On the other hand, if Aut(G) has just one orbit, then Aut(G) is transitive on V, which is not the case. Therefore Aut(G) has exactly two orbits on V. If {u,v} is an edge of G, then there is some g Î Aut(G), such that {u,v}^g = {x,y}. Therefore exactly one of u and v belongs to X and the other belongs to Y. This shows that every edge has exactly one vertex in X and one in Y. ^[¯]