Permutation Groups and the Graph Isomorphism Problem - Perspectives in Computational Complexity - page 179

and any subset T of G that has a unique coset representative from each right coset
is called a right transversal of H in G . Analogously, we define left cosets and left
transversals. In general, the right coset H g and the left coset g H is different. We say
that H is a normal subgroup if g H = H g . We use the notation H G (or G H )

to denote that H is a normal subgroup of G .
A simple group is a group that has no non-trivial normal subgroups. A composition
series of a group G is a tower of subgroups G = G 0 G 1 ··· G t = 1 such

that each of the factor groups G i / G i + 1 , called the composition factors ,aresimple.

The Jordan-Hölder theorem states that for any group G , its composition series is
essentially unique, i.e. any two composition series are of equal length and the list of
composition factors are equal up to a reordering. Solvable groups are those whose
composition factors are abelian.
The set of all permutation of n elements forms a group called the symmetric
group which we denote by S n . In algorithmic settings, it is often useful to make the
domain of n elements explicit: For a finite set ˇ , the set Sym (ˇ) denote the group

of permutations on ˇ .Bya permutation group on ˇ we mean a subgroup of the

symmetric group Sym (ˇ) . As is customary, we use Wielandt's notation [ Wie64 ]:

Let α be any element of , the image of α

under g is denoted by α g . The advantage of this notation is that it follows the familiar
laws of exponentiation:

ˇ and let g be a permutation in Sym (ˇ)

(α g )

h

= α g h . We can extend this notation to (i) subsets of

A

={ α g | g ∗ ʲ g ={ α g | α ∗ ʲ } permutations: α A } , or to (ii) subsets of ˇ : .In

G

particular, for a permutation group on ˇ ,theset α is called the G - orbit of α .Given

G and β G are either disjoint or are the

any two elements α and β of

ˇ

the G -orbits α

ˇ ʲ

same. Thus, orbits of G partition the underlying set . A subset of G is said to be

ʲ g = ʲ G - stable if . Clearly any G -orbit is G -stable. In general, a G -stable set is a

union of G -orbits.
Let G be a permutation group acting on the set ˇ and let ʲ be a subset of ˇ .

The point-wise stabiliser of ʲ is the subgroup of all g in G that is trivial on ʲ , i.e.

α g = α for all α in ʲ .The setwise stabiliser is the subgroup that fixes the set ʲ as

ʲ g = ʲ a whole, i.e it is the subgroup of all g in G such that .

A permutation group G is said to be transitive if the entire set

ˇ is a single

orbit. Equivalently, G is transitive if for any two elements α and β in ˇ there is a

permutation g in G such that α g = β . For a transitive permutation G on

ˇ , a subset

ʲ g is either identical ʲ is said to be a G - block if for any permutation g in G ,theset

to or disjoint from the set .

These blocks are called the trivial blocks of G . For a transitive permutation group
G on

ʲ . Any singleton set is a block and so is the entire set ˇ

ʲ g is a G -block whenever ˇ and a permutation g in G ,theset ʲ itself is

ʲ g is called a conjugate block of one. Such a block ʲ . The family of conjugate

{ ʲ g | g ∗ blocks G } forms a partition of the set ˇ which is called the block system

associated with the block . A permutation group that has no non-trivial block is

called a primitive permutation group . An example of a primitive group is the group
Sym

ʲ

. We have the following lemma about block systems which is more or less
direct from the definition.

(ˇ)