This appendix presents the basic terminology and a few results concerning permutation groups which we shall require in the text. We only scratch the surface of a very rich field indeed. The reader is referred to Biggs and White [15] and to the excellent monograph of Wielandt [141].

A permutation of a finite set X is a one-to-one correspondence g: X→X. Two permutations, g and h, can be composed to give the permutation gh, according to the rule (gh)(x) = g(h(x)). Under this operation, the permutations form a group Sym(X), called the symmetric group on X. When X is a fixed set of cardinality n under discussion, we also denote the symmetric group on these n objects by Sn.

If G is a subgroup of Sym(X) then the pair (G,X) is said to be a permutation group of degree ∥x∥. Or, we say simply that G is a permutation group on X. For each x ε X, the set

Gx = {g(x) ε G}

is called the orbit of x under G. The orbits partition X. The subgroup of all elements of G which leave the element x fixed is called the stabilizer of x; it is denoted by Gx.

Lemma A.1. ∥Gx∥ = [G:Gx].

Proof. Consider the following mapping from G to Gx: map each g ε G to g(x) cGx. The map is onto Gx% Moreover elements of G have the same image if and only if they agree on x– that is, if and only if they are in the same left cost fo Gx.