Chapter 2
Some important classes of vertex-transitive graphs

2.1  Orbital graphs

If G is a permutation group on a set W then we can define a G-action on the set W×W by

(w1,w2)g = (w1g,w2g)   forall   w1, w2 Î W, g Î G.

Exercise 1 Show that this is indeed an action and it is faithful.

The G-orbits on W×W are called the G-orbitals on W. A generalised orbital is a non-empty union of G-orbitals. In particular, an orbital is a generalised orbital. For each generalised orbital D there is a paired generalised orbital D^* defined as

D* = {(b,a) | (a,b) Î D}.

If D = D^* then D is said to be a self-paired generalised orbital.

Lemma 2 If G is transitive on W and a Î W then there is a bijection between the G-orbitals and the orbits of the point stabiliser G_a.

PROOF. We give an explicit bijection j between the set of G-orbitals and the set of G_a-orbits. If D is a G-orbital then set

j(D) = {b | (a,b) Î D}.

First we show that j(D) is G_a-orbit. If b Î j(D) and g Î G_a, then (a,b) Î D and, as D is invariant under the action of G, (a^g,b^g) = (a,b^g) Î D. Thus b^g Î j(D). Therefore j(D) is invariant under the action of G_a. If b₁, b₂ Î j(D) then (a,b₁), (a,b₂) Î D. As D is a G-orbital, there exists a g Î G, such that (a^g,b₁^g) = (a,b₂). This shows that b₁^g = b₂ and a^g = a, and hence g Î G_a. Thus b₁ and b₂ are in the same G_a-orbits. This shows that j(D) is a G_a-orbit.

Let us prove that j is surjective. Let O be a G_a-orbit and suppose that b Î O. Then (a,b) is an element in exactly one of the G-orbitals and O is the image of this orbital. It remains to show that j is injective. Suppose that D₁ and D₂ are G-orbitals, such that j(D₁) = j(D₂). If b Î j(D₁)Çj(D₂) then (a,b) Î D₁ÇD₂. As the orbitals form a partition of W×W, we obtain D₁ = D₂, as required. ^[¯]

Example 3 Let G be a transitive permutation group on W. Then the diagonal set

{(w,w) | w Î W}

is always an orbital and it is called the trivial orbital . Which is the corresponding G_a-orbit?

Example 4 The symmetric group Sym W has only two orbitals. Indeed the diagonal set is an orbital. Suppose that (a₁,a₂) and (a₃,a₄) Î W×W, such that a₁ ¹ a₂ and a₃ ¹ a₄. Then it is easy to see that there is always a permutation p, such that a₁^p = a₃ and a₂^p = a₄. That is (a₁,a₂) and (a₃,a₄) are in the same G-orbit. This shows that there are exactly two orbitals.

The previous example can be generalised. A permutation group G on W is said to be 2-transitive if it is transitive on the set of pairs (a,b), such that a ¹ b. By definition, a 2-transitive group always has only two orbitals.

Example 5 Let G be the cyclic group generated by the permutation (1,2,3,4,5,6) acting naturally on W = {1,2,3,4,5,6}. Then an easy computation shows that G has five non-trivial orbitals, namely

{ ( 1, 2 ), ( 3, 4 ), ( 5, 6 ), ( 2, 3 ), ( 4, 5 ), ( 6, 1 ) }, { ( 1, 3 ), ( 3, 5 ), ( 5, 1 ), ( 2, 4 ), ( 4, 6 ), ( 6, 2 ) }, { ( 1, 4 ), ( 3, 6 ), ( 5, 2 ), ( 2, 5 ), ( 4, 1 ), ( 6, 3 ) }, { ( 1, 5 ), ( 3, 1 ), ( 5, 3 ), ( 2, 6 ), ( 4, 2 ), ( 6, 4 ) }, { ( 1, 6 ), ( 3, 2 ), ( 5, 4 ), ( 2, 1 ), ( 4, 3 ), ( 6, 5 ) }.

Example 6 Let G be the dihedral group of order 8 acting on W = {1,2,3,4}. That is G can be generated by the permutations (1,4)(2,3) and (1,2,3,4). Then W×W is a set of 16 elements and one can easily see that the non-trivial G-orbits on W×W are

{( 1, 2 ), ( 4, 3 ), ( 2, 1 ), ( 3, 4 ), ( 1, 4 ), ( 2, 3 ), ( 4, 1 ), ( 3, 2 )}   and   {( 1, 3 ), ( 4, 2 ), ( 2, 4 ), ( 3, 1 )}

We can also use this example to illustrate the previous lemma. The stabiliser G₁ of the point 1 in G is the subgroup {(),(2,4)}. The subgroup G₁ has 3 orbits on W, namely {1}, {2,4}, and {3}. The orbital corresponding to {1} is the G-closure of the element (1,1). This is the diagonal orbit {(1,1),(2,2),(3,3),(4,4)}. The orbital corresponding to the orbit {3} is the G-closure of the pair (1,3). This is {( 1, 3 ), (4, 2 ), ( 2, 4 ), ( 3, 1 )}. Finally the orbital corresponding to the orbit {2,4} is the G-closure of {(1,2),(1,4)}. It is easy to see that this is {( 1, 2 ), ( 4, 3 ), ( 2, 1 ), ( 3, 4 ), ( 1, 4 ), ( 2, 3 ), ( 4, 1 ), ( 3, 2 )}.

For a given generalised orbital D we construct the so-called generalised orbital di-graph G whose vertex set is W and arc set is D. If D is an orbital then G is called an orbital di-graph . It is easy to see that G is a graph if and only if D is self-paired and does not contain the trivial orbital.

Example 7 Let G be the dihedral group of order 16, as in the previous example. Then the graph corresponding to the orbital O₁ is the graph G₂ on Figure 1.3. The graph corresponding to theorbital O₂ is the following graph:

If G is a subgroup of Sym W and G is a generalised orbital di-graph corresponding to a G-orbital on W, then it is easy to see that G is a subgroup of Aut(G). Conversely, let G = (V,E) be a di-graph and G a subgroup of Aut(G). Then E must be a generalised G-orbital on V. Hence the following theorem is true.

Theorem 9 Let G = (V,E) be a di-graph and G a subgroup of Sym V. Then G is a group of automorphisms for G if and only if G is isomorphic to a generalised orbital di-graph for G.

If G is an orbital di-graph, then G acts transitively on the arc set of G, and so G is an arc-transitive subgroup of Aut(G). Conversely, if G = (V,E) is a di-graph and G is an arc-transitive subgroup of Aut(G), then E must be a G-orbital on V. This leads to the following theorem.

Theorem 10 Let G = (V,E) be a di-graph and G £ Sym V. Then G is an arc-transitive group of automorphisms of G if and only if G is isomorphic to an orbital di-graph for G.

2.2  Cayley graphs and di-graphs

Now we have a look at another class of di-graphs which can be constructed from a given group.

Let G be a group and S a subset of G. The Cayley di-graph of G with respect to S is defined as the di-graph G = (G,E), where E is a subset of G×G, such that

(u,v) Î E   if and only if there exists some s Î S, suchthat     v = su.

Informally speaking, the vertices of the Cayley di-graph are the group elements, and two vertices are connected with an arc if and only if the second vertex is the product of an element from S and the first vertex. The Cayley di-graph of G with respect to S is denoted by Cay(G,S).

Exercise 11 Prove that Cay(G,S) is a graph if and only if both of the following conditions hold:

(i) S does not contain the identity element;
(ii) S is closed under taking inverses - that is, s Î S if and only if s^-1 Î S for all s Î G.

If Cay(G,S) is a graph then we call it the Cayley graph of G with respect to S.

Example 12 Draw the Cayley di-graph of the following groups with respect to the given set S:

(i) G = S₃, S = {(1,2,3)};
(ii) G = S₃, S = {(123),(132),(12)};
(iii) G = A₄, S = {(123),(132),(12)(34)};
(iv) G = Z_2n, S = {[`1],-[`1]}
(v) G = Z_2n, S₂ = {[`1],-[`1],[`n]};
(vi) G = Z<sub>n</sub>×Z<sub>2</sub>; S = {([`1],[`0]),(-[`1],[`0]), ([`0],[`1])};

As one of the previous examples shows, Cay(G,S) need not be connected. The following result gives a sufficient and necessary condition for the Cayley di-graph to be connected.

Lemma 13 The di-graph Cay(G,S) is connected if and only if S generates G.

PROOF. Suppose that S generates G. Then each element g of G can be written as g = s_n¼s₁ where either s_i Î S or s_i^-1 Î S for all i Î {1,¼,n}. Then it is easy to see that (1,s₁,s₂s₁,¼,s_n¼s₁) is a path from 1 to g. Thus every element of G is connected to 1 with a path, and hence G is connected.

Conversely suppose that G = Cay(G,S) is connected. Then for each g Î G there is a path

(g0 = 1,g1,¼,gn = g).

(2.1)

We claim that each element g_i in this path lies in the subgroup < S > of G generated by S. We prove this by induction on i. For i = 0, the element 1 is clearly contained in < S > . Suppose that the claim holds for some i Î {0,¼,n-1} and prove it for i+1. Then, as (2.1) is a path, we have that either (g_i,g_i+1)or (g_i+1,g_i) is an arc of G. In the first case there is some s Î S, such that g_i+1 = sg_i. As g_i, s Î < S > , we have that g_i+1 Î < S > . In the second case g_i = sg_i+1 for some s Î S, and so g_i+1 = s^-1g_i Î < S > . ^[¯]

Exercise 14 Generalise the previous lemma. Show that if H is the subgroup of G generated by S, then the subgraph spanned by H is the connected component of 1 in Cay(G,S). This is itself a Cayley di-graph Cay(H,S).

Lemma 15 Let G be a group and S a subset of G. Then the group G is a vertex-transitive subgroup of Aut(Cay(G,S)).

PROOF. Recall that G has an action on itself in which every element acts by right multiplication. We only have to show that this action preserves the di-graph Cay(G,S). If (u,v) is an arc in the Cayley di-graph Cay(G,S), then there is some s Î S such that v = su. If g Î G then the image of this arc under the action of g is (ug, vg). As v = su, we obtain vg = (su)g = s(ug), that is (ug,vg) = (u,v)^g Î E. Therefore g induces an automorphism of Cay(G,S), as required. ^[¯]

Exercise 16 What are the in-valency and the out-valency of Cay(G,S)?

The previous lemma shows that Aut(Cay(G,S)) has a regular subgroup, namely the image of G in its right-regular representation. The following theorem, which was discovered by Sabiddusi in 1956, shows that the converse is also true.

Theorem 17 A di-graph G is a Cayley di-graph if and only if Aut(G) contains a subgroup which is regular on the vertices.

PROOF. We have already seen in Lemma 2.15, that if G is a Cayley di-graph of G, then Aut(G) has a regular subgroup isomorphic to G. Conversely, let G = (V,E) be a di-graph, and suppose that Aut(G) has a subgroup G that is regular on the vertices. Suppose that V has n elements and V = {v₁,v₂,...,v_n}. Then, as G is regular on V, for each v_i, there exists exactly one element g_i Î G such that v₁^g_i = v_i. Set S = {g_i Î G | (v₁,v_i) Î E}. Then we claim that the map

s:  gi ® vi,   i Î {1,2,...,n}

is an isomorphism from Cay(G,S) to the di-graph G. Indeed,

(vi,vj) Î E Û (v1gi,v1gj) Î E Û (v1,v1gjgi-1) Î E Û gjgi-1 Î S Û gj = sgi for some s Î S Û (gi, gj) is an edge of Cay(G,S).

^[¯]

As the previous results show, Cay(G,S) is vertex-transitive. When is it arc-transitive? This question can sometimes be decided by looking at the group theoretical properties of G and S. Let us first define a subgroup Aut(G,S) of Aut(G), such that Aut(G,S) consists of those automorphisms of G that fix the set S. Formally,

Aut(G,S) = {s Î Aut(G) | ss Î S for all s Î S}.

Using Aut(G,S) we can give a sufficient condition for Cay(G,S) to be arc-transitive.

Lemma 18 For a Cayley di-graph G = Cay(G,S), we have that Aut(G,S) is a subgroup of the stabiliser of 1 in Aut(G). Furthermore, if Aut(G,S) is transitive on S, then G is arc-transitive.

PROOF. If a Î Aut(G,S), then a is a permutation of G which fixes the identity element 1 of G. In order to show that a is a graph automorphism, it suffices to prove that for all g₁, g₂ Î G, (g₁,g₂) is an arc of G if and only if (g₁^a,g₂^a) is an arc. Using that a permutes S, this is an easy calculation and is left to the reader.

Note that

S = {g Î G | (1,g) is an arc of Cay(G,S)}.

If Aut(G,S) is transitive on S, then the point stabiliser of 1 in Aut(Cay(G,S)) is also transitive on the neighbours of 1. Using Lemma 1.28 we obtain that Aut(Cay(G,S)) must bearc-transitive. ^[¯]

This result has an important corollary for graphs with an abelian group of automorphism. For a prime p, finite group G is called an elementary abelian p-group if G is abelian and g^p = 1 for all g Î G.

Theorem 19 Let G = (V,E) be a graph, and suppose that Aut(G) is abelian and vertex-transitive. Then Aut(G) is an elementary abelian 2-group and it acts regularly on V.

PROOF. By Exercise 1.11, the group Aut(G) is regular on the vertices and, by Theorem 2.17, G is a Cayley di-graph for Aut(G) with respect to some set S. So we only have to prove that Aut(G) is an elementary abelian 2-group. As Aut(G) is abelian, the map g® g^-1 is an automorphism of Aut(G) and, as G is a graph, it fixes S setwise. So this map is a graph automorphism fixing the identity element 1. On the other hand, Aut(G) is regular and it follows that the automorphism g® g^-1 must be trivial. Hence g = g^-1 for all g Î G, and so g² = 1 as required. ^[¯]

2.3  Equivalent actions

Suppose that the group G acts transitively on a set W and let w be a point of W. Then we have seen that there is a one-to-one correspondence between W and the set [G:G_w] of right cosets of G_w. Moreover there is a natural G action of G on [G:G_w]. Our aim is to show that these two actions are essentially the same.

Let us consider an example. Let G = S₃ acting naturally on W = {1,2,3}. Then a point stabiliser G₁ is the subgroup < (2,3) > . Moreover G₁ has three right cosets in G, namely {(),(2,3)}, {(1,2),(1,2,3)}, and {(1,3,2),(1,3)}. The bijection defined in Exercise 1.8 is

1® {(),(2,3)},    2®{(1,2),(1,2,3)},   3®{(1,3,2),(1,3)}.

Let us denote this bijection by j. It is an easy hand computation to check that for all g Î G and w₁, w₂ Î W we have that w₁^g = w₂ if and only if j(w₁)^g = j(w₂). Indeed this correspondence can be verified for all 6 elements of G and all 9 possibilities for w₁, w₂.

Let G be acting on two sets W and S. We say that these two actions are equivalent if there is a bijection j:W®S, such that for all g Î G and w Î W we have that

j(wg) = j(w)g

(2.2)

The map j is sometimes called an equivalence or permutation equivalence between the two actions.

Exercise 20 Show that for a given group G, the equivalence of actions is a equivalence relation on the set of all G-actions.

After carefully studying the previous example, the proof of the following theorem is an easy exercise. However, the importance of this result justifies including its proof here.

Theorem 21 Let G be a a group acting transitively on a set W, and let w Î W. Then this action of G is equivalent to its coset action on [G:G_w].

PROOF. In Exercise 1.8 we defined a bijection j between W and [G:G_w], as j(w¢) = {g | w^g = w¢} for all w¢ Î W. We show that j is an equivalence between the two actions. As we have already seen that j is a bijection, it suffices to prove that j satisfies (2.2). Suppose that g Î G and w Î W. Then we have to prove that

{g Î G | wg = w1}g = {g Î G | wg = w2}.

It is an easy computation, and is left to the reader. ^[¯]

As every transitive action is equivalent to a coset action, we might ask when two coset actions are equivalent. The answer is given by the following theorem

Theorem 22 Let G be a group and H₁ and H₂ subgroups of G. Then the coset actions of G on [G:H₁] and [G:H₂] are equivalent if and only if H₁ and H₂ are conjugates in G.

PROOF. If H₁ and H₂ are conjugates, then there is some element g Î G, such that H₁^g = H₂. First we define a bijection j:[G:H₁]® [G:H₂], by setting

j(H1x) = H2g-1x   for all    x Î G.

First we have to show that j is well-defined. In other words, if H₁x₁ = H₁x₂ then j(H₁x₁) = j(H₁x₂). If H₁x₁ = H₁x₂, then x₁x₂^-1 Î H₁, therefore we also have (x₁x₂^-1)^g = g^-1x₁x₂^-1g Î H₂. That is, H₂ = H₂g^-1x₁x₂^-1g, and so H₂g^-1x₂ = H₂g^-1x₁, and hence j(H₁x₁) = j(H₁x₂) as required. If H₂y Î [G:H₂] then H₂y = j(H₁gy), which implies that j is surjective. As |G:H₁| = |G:H₂|, we also have that j must be injective, and therefore it is a bijection. We only have to verify that j is a permutation equivalence. This easily follows, because for all x, h Î G we have

j((H1x)h) = j(H1xh) = H2g-1xh = (H2g-1x)h = j(H1x)h.

Now assume that H₁ and H₂ are subgroups of G, such that the coset actions of G on [G:H₁] and [G:H₂] are equivalent and j is a permutation equivalence between [G:H₁] and [G:H₂]. Then H₂ Î [G:H₂] and there is some x Î G, such that H₂ = j(H₁x). As j is a permutation equivalence, an element g Î G fixes H₂ if and only if it fixes H₁x. The elements of G that fix H₂ in its action on [G:H₂] are exactly the ones that belong to H₂. This implies that H₂ is the point stabiliser of H₁x in the G-action on [G:H₁]. As this action is transitive, H₂ must be a conjugate to H₁ (recall Exercise 1.8). ^[¯]

The last two results show that for a given group G there is a bijection between the equivalence classes of transitive G-actions and the conjugacy classes of subgroups in G. If one known the conjugacy classes of such subgroups, then one can describe each G-action up to equivalence.

Exercise 23 Find all equivalence classes of transitive permutation representations of A₄. Find a geometric interpretation for each class.