Graphs and groups

July 3, 2008

Graphs from groups

Let G be a group, H a subgroup, and X some subset of G. We can define a graph Γ = Γ(G, H, X) by taking as vertex set the collection {gH | g ∈ G} of left cosets of H, and letting two vertices g_{1}H and g_{2}H be adjacent when Hg_{2}^{−1}g_{1}H ⊆ HXH.

(Now adjacency is well-defined: it does not depend on the chosen representative g of the coset gH.)

The group G acts transitively on Γ(G, H, X) via left multiplication: g ∈ G sends the coset aH to gaH. Indeed, this map preserves adjacency.

Conversely, if Γ is an arbitrary graph with transitive group of automorphisms G, then we can fix some vertex p of Γ and let H be the stabilizer of p in G. Now, for some suitable X, Γ is of the form Γ(G, H, X).

Primitive actions

Let G be a permutation group, acting on a set Ω. The permutation action is called primitive when there is no nontrivial partition of Ω that is preserved by G. (Trivial partitions are the partition into singletons and the partition into one big piece.)

If H is not maximal, say H < B < G then {{gbH | b ∈ B} | g ∈ G} is a nontrivial partition of the vertex set of Γ(G, H, X), and the representation of G on the vertices of Γ(G, H, X) is not primitive.

Conversely, a primitive permutation action of a transitive permutation group belongs to a maximal subgroup. (Indeed, let us call the parts of a nontrivial partition preserved by G blocks. If B is a block, then for b_{1}, b_{2} ∈ B we see that b_{2}^{−1}b_{1}B = B so that B is a coset of a subgroup.)

Imprimitive actions are precisely the actions for which one can pick a nonempty X such that the graph Γ(G, H, X) is disconnected.

Several subgroups

If G has several maximal subgroups, and one is chosen as vertex stabilizer H, then the other subgroups have some permutation action on the set of cosets G/H and hence on the graph Γ(G, H, X). It is a game to recognize all maximal subgroups from substructures of the graph Γ.

Petersen

An example. Let G be the symmetric group S_{5} of order 120. It has three maximal subgroups, namely S_{4} and AGL(1, 5) and 2 × S_{3}, where AGL(1, 5) denotes the affine group of transformations x ↦ ax + b, with a, b, x ∈ F_{5}, a ≠ 0. These subgroups have orders 24 and 20 and 12, and hence have index 5 and 6 and 10, respectively.

Thus, one obtains a graph on 10 vertices if one chooses H = 2×S_{3} (whether one gets Petersen or its complement, the triangular graph T (5), or the complete graph, or the cocomplete graph, depends on the choice of X).

Choose X, and H = 2 × S_{3}, so as to obtain the Petersen graph Γ. What substructures correspond to the maximal subgroups of G? For 2 × S_{3} one finds a vertex. For S_{4} one finds a 4-coclique. For the third group AGL(1, 5) one finds a partition of the graph into two pentagons.

(Indeed, the vertices of Petersen are the pairs from a 5-set, adjacent when disjoint. Now S_{4} preserves one symbol, so has orbits of lengths 4 + 6 on the 10 vertices, and the orbit of length 4 is a 4-cocliqe. And AGL(1, 5) has orbits of lengths 5 + 10 on the 15 edges of the Petersen graph, where the orbit of length 5 is a matching that splits the graph into two pentagons.)

Permutation character

Recall that if G acts as a group of permutations on a set Ω, then the corresponding permutation character is the function π : G → N defined by π(g) = #{ω ∈ Ω | gω = ω}, the number of fixpoints of g in this action.

The inproduct ⟨1, π⟩ is the number of orbits of G.

If G is transitive, then the inproduct ⟨π, π⟩ is the rank of the action, the number of orbits of a point stabilizer.

If H_{1} and H_{2} are two subgroups of G, and the permutation actions of G on G/H_{1} and G/H_{2} have permutation characters π_{1} and π_{2}, respectively, then ⟨π_{1}, π_{2}⟩ is the number of cosets gH_{1} fixed by H_{2} (and the number of cosets gH_{2} fixed by H_{1}).

Results like these are proved using Frobenius reciprocity, see the notes on representations of finite groups.

Now S_{5} has character table

1 (12)(34) (123) (12345) (12) (1234) (12)(345)
χ_{1} 1  1  1  1  1  1  1
χ_{2} 1  1  1  1  −1  −1  −1
χ_{3} 4  0  1  −1  2  0  −1
χ_{4} 4  0  1  −1  −2  0  1
χ_{5} 5  1  −1  0  1  −1  1
χ_{6} 5  1  −1  0  −1  1  −1
χ_{7} 6  −2  0  1  0  0  0

and the three subgroups S_{4}, AGL(1, 5), 2 × S_{3} have permutation characters π_{1} = χ_{1} + χ_{3} and π_{2} = χ_{1} + χ_{6} and π_{3} = χ_{1} + χ_{3} + χ_{5}, respectively.

The fact that (π_{1}, π_{1}) = (π_{2}, π_{2}) = 2 means that these are 2-transitive representations: one does not obtain a graph other than the complete or cocomplete graphs, the only two relations are being equal or distinct. The fact that (π_{3}, π_{3}) = 3 means that the stabilizer of a vertex in the Petersen graph has three orbits: that vertex, its neighbours, and its nonneighbours, so that the Petersen graph is strongly regular.

The fact that (π_{2}, π_{3}) = 1 means that a vertex stabilizer of Petersen still is transitive on the 6 objects permuted by AGL(1, 5). Thus, these objects are not described by special subsets of Petersen but by something homogeneous—in this case a partition into two pentagons.

If one restricts to the alternating group A_{5}, then χ_{5} and χ_{6} coincide, and we do get special subsets, namely two orbits of six pentagons.