± ∈ „¦, the digraph has in-degree and out-degree 1 and so is a disjoint union of

cycles; this is precisely the cycle decomposition.

The generalisation to permutation groups is the orbit decomposition, which

we now discuss.

A permutation group G on a set „¦ is a subgroup of the symmetric group on

„¦; that is, it is a set of permutations closed under composition and inversion and

containing the identity permutation. The degree of the permutation group G is

|„¦|.

Let G be a permutation group on „¦. De¬ne a relation ∼G on „¦ by the rule

that ± ∼G β if there exists g ∈ G with ±g = β. It is easy to see that ∼G is an

equivalence relation; the re¬‚exive, symmetric and transitive laws follow from the

identity, inverse, and composition properties of G. The equivalence classes of ∼G

are called the orbits of G,, and G is said to be transitive if there is a single orbit,

intransitive otherwise.

Note that G is transitive if and only if, for all ±, β ∈ „¦, there exists g ∈ G

which maps ± to β.

The stabiliser of a point ± ∈ „¦ is the subgroup

G± = {g ∈ G : ±g = ±}.

Now, if β is any point of „¦, then the set

X(±, β) = {g ∈ G; : ±g = β}

is either empty (if ± and β lie in different orbits) or a right coset of G± . We

see that the number of right cosets is equal to the size of the orbit. This is the

Orbit-Stabiliser Theorem:

Theorem 5.1 Let ∆ be an orbit of the permutation group G, and ± a point of ∆.

Then

|G± | · |∆| = |G|.

But this is more than a counting result. Suppose that the group G acts as a

permutation group on two different sets „¦1 and „¦2 . We say that the actions are

isomorphic if there is a bijection θ : „¦1 ’ „¦2 such that

(±θ)g = (±g)θ

5.1. Orbits and stabiliser 35

for all ± ∈ „¦1 and g ∈ G. In other words, if we identify „¦1 and „¦2 according

to the bijection θ, then the permutations corresponding to any group element are

identical.

Now let H be a subgroup of G. The coset space G : H is de¬ned to be the

set of right cosets of H in G. Now G acts as a permutation group on G : H by

the following rule: group element g acts as the permutation Hx ’ Hxg. (This is

clearly well de¬ned, independent of the choice of coset representative x.) Now

the re¬ned version of the Orbit-Stabiliser Theorem states:

Theorem 5.2 Let ∆ be an orbit of the permutation group G, and ± a point of ∆.

Then the actions of G on ∆ and on the coset space G : G± are isomorphic.

The isomorphism is given by βθ = X(±, β) in the earlier notation. The proof

is an exercise.

It can also be shown that two coset spaces G : H and G : K provide isomorphic

actions of G if and only if the subgroups H and K are conjugate, that is, K =

g’1 Hg for some g ∈ G.

Thus, to classify the transitive actions of G up to isomorphism, we list a set of

representatives of the conjugacy classes of subgroups, and form the coset spaces.

To classify all permutation actions, we take arbitrary disjoint unions of the transi-

tive ones.

A permutation group G is semiregular if the stabiliser of any point is the iden-

tity. It is regular if it is semiregular and transitive. By Theorem 5.2, any regular

action of G is isomorphic to the action of G on itself by right multiplication (with

„¦ = G, where g ∈ G induces the permutation x ’ xg).

Let G be a permutation group on „¦. Suppose that the set ∆ ⊆ „¦ is invariant

under G (that is, ¬xed setwise “ this happens if and only if ∆ is a union of orbits

of G). Then G∆ denotes the group of permutations of ∆ induced by elements of

G. It is a homomorphic image of G; the kernel of the homomorphism is the set of

permutations which ¬x every point in ∆.

Now suppose that (∆i : i ∈ I) are the orbits of G. For each i, let Gi = G∆i . The

permutation groups Gi are called the transitive constituents of G.

Then G is a subgroup of the Cartesian product ∏i∈I Gi of the subgroups Gi .

Since we are only concerned with ¬nite permutation groups, the set I is ¬nite, and

the Cartesian product is more usually referred to as the direct product, and written

G1 — · · · — Gr ,

where I = {1, . . . , r}. Note that G may not be equal to the direct product! In this

sense, the orbit decomposition allows many questions about permutation groups

to be “reduced” to questions about transitive groups, but there is a dif¬culty go-

ing back: a permutation group is not uniquely determined by its transitive con-

stituents.

36 Chapter 5. Permutation groups

Now let ∆ be any subset of „¦. Then G∆ denotes the setwise stabiliser of

∆, the set of permutations which map the set ∆ to itself; and G(∆) denotes the

pointwise stabiliser of ∆, the set of permutations which ¬x every point of „¦, so

that G(∆) = ±∈∆ G± ).

Thus G∆ is the permutation group induced on ∆ by its setwise stabiliser in G,

∆

and is isomorphic to G∆ /G(∆) . This group will be important in the ¬nal chapter.

To avoid the double subscript, we denote it by G[∆].

We conclude this section with another piece of terminology. Let Gi be a per-

mutation group on „¦i for i = 1, 2. We say that G1 and G2 are isomorphic as

permutation groups if there is a bijection θ : „¦1 ’ „¦2 and a group isomorphism

φ : G1 ’ G2 such that

(±g)θ = (±θ)(gφ)

for all ± ∈ „¦1 and g ∈ G1 . If two actions of the same group are isomorphic accord-

ing to the earlier de¬nition, then the induced permutation groups are isomorphic

as permutation groups; but the converse is false, since we now permit an automor-

phism of G.

For example, let G = C2 —C2 be generated by elements a and b. The actions

given by

a = (1, 2), b = (3, 4)

and

a = (1, 2)(3, 4), b = (3, 4)

are not isomorphic, but their images are isomorphic (indeed, identical) as permu-

tation groups.

5.2 The Orbit-Counting Lemma

The Orbit-Counting Lemma (incorrectly called Burnside™s Lemma in much of

the literature of combinatorial enumeration) is a simple relationship between ¬xed

points and orbits of a permutation group, which will be crucial in what follows.

Let G be a permutation group on „¦. For g ∈ G, let ¬x(g) denote the number

of points of „¦ ¬xed by g. Now the Orbit-Counting Lemma states:

Theorem 5.3 The number of orbits of a permutation group G is equal to the av-

erage number of ¬xed points of its elements: that is, the number of orbits is

1

‘ ¬x(g).

|G| g∈G

5.2. The Orbit-Counting Lemma 37

Proof Construct a bipartite graph as follows. The vertex set is „¦ ∪ G; there is an

edge from ± ∈ „¦ to g ∈ G if and only if g ¬xes ±.

To prove the theorem, we count the edges of the graph in two different ways.

Clearly the vertex g lies on ¬x(g) edges, and so the number of edges is

‘ ¬x(g).

g∈G

On the other hand, the vertex ± lies on |G± | edges. By the Orbit-Stabiliser Theo-

rem 5.1, if ∆ is the orbit containing ±, then

|G± | · |∆| = |G|,

so the number of edges containing a vertex in ∆ is equal to |G|, and the total

number of edges is |G| times the number of orbits.

Equating these two numbers gives the result.

For example, the symmetric group S4 contains one element with four ¬xed

points; six elements (the transpositions) with two ¬xed points; eight elements (the

3-cycles) with one ¬xed point; and nine elements (the 4-cycles and the double

transpositions) with no ¬xed points. So the number of orbits is

1

(1 · 4 + 6 · 2 + 8 · 1 + 9 · 0) = 1.

24

Corollary 5.4 If G is a transitive permutation group of degree n > 1, then G

contains an element with no ¬xed points.

Proof The average number of ¬xed points is one; the identity ¬xes more than

one point; so some element ¬xes fewer than one.

This result is due to Jordan. Despite its simplicity, it has a variety of applica-

tions in number theory and topology: a recent paper of Serre [28] describes some

of these.

In combinatorial enumeration, it is often the case that being able to count the

members of a set and being able to choose one at random are closely related. This

principle applies to the Orbit-Counting Lemma, as observed by Mark Jerrum [20].

Consider the following Markov chain, de¬ned on the elements of „¦. In one

step, we move from a point ± to a randomly chosen neighbour of ± in the bipartite

graph of Theorem 5.3 (that is, an element g ∈ G± ), and then to a randomly chosen

neighbour β of g (that is, a ¬xed point of g).

38 Chapter 5. Permutation groups

Since it is possible to move from any point ± to any point β in a single step

(via the identity of G), the chain is irreducible and aperiodic; so there is a unique

limiting distribution, to which it converges from any initial distribution. This dis-

tribution is easily seen to have the property that the probability of ± is inversely

proportional to the size of the orbit containing ±; in other words, the limiting

distribution is uniform on orbits.

It is important to know the mixing time of such a Markov chain, that is, how

rapidly it approaches its limit, and in particular to characterise the permutation

groups for which the chain is rapidly mixing. Very little is known about this!

5.3 Bases and strong generating sets

In practice, one needs a computer to investigate permutation groups. Even

groups of moderate degree can be very large, and ¬nding interesting subgroups

by hand if we are given a set of permutations generating the group is a daunting

task. On the other hand, there are very ef¬cient algorithms for computing with

permutation groups, and it is possible to study groups with degrees in the tens of

thousands without too much trouble.

In this section, we take the ¬rst steps in computational permutation group

theory. We are given a set S of permutations which generate a subgroup G of

Sn , and we want to be able to do such things as ¬nd the order of G, choose a

random element of G (from the uniform distribution), or test an element of Sn for

membership in G.

The ¬rst thing we can do is to ¬nd the orbits of G. For consider the directed

graph on „¦ with edges (±, ±s) for all ± ∈ „¦ and s ∈ S. The orbits are precisely

the connected components of this graph. Moreover, for each point in the orbit of

±, we can ¬nd a witness, an element of G (in the form of a word in the generators

S) mapping ± to β. These witnesses form a set X of coset representatives for G±

in G.

Next, a lemma of Schreier shows that, if generators of a group and coset rep-

resentatives for a subgroup are known, then generators for the subgroup can be

computed.

Now we apply this procedure recursively until the group is trivial. At this

point, what we have found is the following:

(a) a base for G; that is, a sequence (±1 , . . . , ±r ) of points of „¦ whose pointwise

stabiliser is the identity;

(b) for i = 1, . . . , r, a set Xi of coset representatives for Gi’1 in Gi , where Gi is

the pointwise stabiliser of (±1 , . . . , ±i ).

Now this information enables us to settle the above questions. We begin with

5.3. Bases and strong generating sets 39

the membership test. Suppose that a permutation g ∈ Sn is given. If G is the trivial

group, we can decide immediately whether g ∈ G. Suppose not. We compute ±1 g.

If this is not in the G-orbit of ±1 , then g ∈ G, and we are done. Otherwise, there

/

is a unique x1 ∈ X1 such that ±1 g = ±1 x1 . Now gx1 ¬xes ±1 , and we apply the

’1

’1

test recursively to decide whether gx1 ∈ G1 ; for we have g ∈ G if and only if

’1

gx1 ∈ G1 in this case.

If the test succeeds, then we will eventually ¬nd that

’1 ’1

gx1 · · · xr = 1,

that is, g = xr · · · x1 , with xi ∈ Xi for i = 1, . . . , r. This expression is unique, so

|G| = |Xr | · · · |X1 |,

and we have found the order of G. This can also be seen by noting that |Xi | =

|Gi’1 : Gi |, and of course

|G| = |G0 : G1 | · · · |Gr’1 : Gr |,

since G0 = G and Gr = 1.

The equation

G = Xr · · · X1

shows that the union of the sets X1 , . . . , Xr generates G; similarly, for any i, the set

Xi+1 ∪ · · · ∪ Xr generates Gi . The set X = X1 ∪ · · · ∪ Xr is called a strong generating

set for G.

The unique representation also shows that if we choose elements uniformly

and independently at random from Xr , . . . , X1 and multiply them, we obtain a uni-

form random element of G.

We will have more to say about bases later, so we pursue the subject a little

further here. First, we note another property of bases relevant to computational

group theory. Any element g ∈ G is determined uniquely by the image of a base B

under g; for, if Bg = Bh, then Bgh’1 = 1, so that gh’1 = 1 (by de¬nition of a base),

and g = h. Thus, it is of interest to ¬nd the smallest possible base. Unfortunately,

Kenneth Blaha [1] showed that this problem is NP-complete in general; but there

are some things we can say.

When we are choosing a base, there is clearly no point in choosing a point ±i

which is ¬xed by the stabiliser of its predecessors. So we call a base irredundant

if no base point is ¬xed by the stabiliser of its predecessors. Usually we consider

only irredundant bases.

Unlike vector spaces, permutation groups can have bases of different cardinal-

n

ities. Consider, for example, the group C2 , acting with n + 1 orbits as follows: for

40 Chapter 5. Permutation groups

each i ¤ n, an orbit Oi of size 2 on which all generators except the ith act trivially;

and an orbit O0 of length 2n on which the group acts regularly. Choose ±i ∈ Oi

for each i. Then, for 1 ¤ i ¤ n, there is an irredundant base of size i of the form

(±1 , . . . , ±i’1 , ±0 ).

On the other hand, there are some restrictions:

Proposition 5.5 The number r of elements in an irredundant base for a permuta-

tion group G of degree n satis¬es

log |G|/ log n ¤ r ¤ log |G|/ log 2.

Proof We have

|G| = |G0 : G1 | · · · |Gr’1 : Gr |.

Each index |Gi’1 : Gi | is at least 2 (since the base is irredundant) and at most n

(since it is the length of an orbit of Gi’1 ). So

2r ¤ |G| ¤ nr ,

and we are done.

Our earlier example shows that in general no substantial improvement can be

made.

5.4 Primitivity and multiple transitivity

Some transitive groups can be further “reduced”.

Let G be a transitive permutation group on „¦. A G-congruence is an equiv-

alence relation on „¦ which is preserved by G. Its equivalence classes form a

partition of „¦ whose parts are permuted among themselves by G. The set of

equivalence classes is called a system of imprimitivity, and the classes are blocks

of imprimitivity.

A congruence (or the associated system or blocks of imprimitivity) is called

trivial if either it is the relation of equality, or it is the “universal” relation „¦ —

„¦. Every group preserves the trivial congruences. If there is a non-trivial G-

congruence, then G is said to be imprimitive; otherwise it is primitive.

Note that we have de¬ned these terms only for transitive permutation groups

(see Exercise 5.5). Thus, all the equivalence classes of a G-congruence have the

same size. In particular, any transitive permutation group of prime degree is prim-

itive.

If G is imprimitive, let S be a system of imprimitivity, and B one of its blocks.

From G, we construct two smaller permutation groups:

5.5. Modern permutation group theory 41

(a) K = GS , the group of permutations of S induced by G;

(b) H = GB = G[B], the group of permutations of B induced by its setwise sta-

B

biliser in G.

Each of these groups is transitive, and it can be shown that G is isomorphic to a

subgroup of the wreath product H Wr K. Continuing this reduction if H or K is

imprimitive, we end up with a sequence of primitive groups called the primitive

components of G.

The next result gives some basic properties of primitive groups.

Proposition 5.6 (a) A transitive permutation group G is primitive if and only if

G± is a maximal subgroup of G.

(b) Let N be a non-trivial normal subgroup of the transitive group G. Then

the orbits of N form a system of imprimitivity for G. In particular, if G is

primitive, then any non-trivial normal subgroup of G is transitive.

Let t be a positive integer, at most |„¦|. The permutation group G on „¦ is said

to be t-transitive if we can map any t-tuple of distinct elements of „¦ to any other

such t-tuple by some element of G. We say that G is multiply transitive if it is

t-transitive for some t > 1.

The problem of determining the multiply transitive permutation groups goes

back to the origins of group theory in the nineteenth century: Galois knew of the

existence of 2-transitive groups PSL(2, p), and Mathieu constructed 5-transitive

groups M12 and M24 . The condition of t-transitivity becomes stronger as t in-

creases. The symmetric group Sn is n-transitive, and the alternating group An is

(n ’ 2)-transitive.

However, a de¬nitive result had to wait for the Classi¬cation of Finite Sim-

ple Groups (CFSG), as we will see in the next section. Using this classi¬cation,

all multiply transitive groups have been determined. In particular, the only 5-

transitive groups apart from symmetric and alternating groups are the two Mathieu

groups mentioned above.

5.5 Modern permutation group theory

The title of this section is taken from a talk by Michael Aschbacher to the

London Mathematical Society in 2001. Aschbacher™s theme was that many ques-

tions about ¬nite permutation groups can be reduced to questions about almost

simple groups (where a group is said to be almost simple if it is an extension of a

non-abelian simple group by a subgroup of its outer automorphism group). Now

the ¬nite simple groups have been classi¬ed (though a complete proof has not yet

42 Chapter 5. Permutation groups

been published, so the proof of this claim is not open to scrutiny), and detailed

properties of the known simple groups have been worked out, so such questions

can often be settled.

The Classi¬cation of Finite Simple Groups, which we abbreviate to CFSG, is

an enormously complicated theorem; the ¬rst complete published proof will cover

many thousands of pages. So for several reasons it is prudent to label clearly a

result proved using CFSG. See Gorenstein [15] for an introduction to the ¬nite

simple groups and to the proof of CFSG.

The reduction works as follows. We have seen a reduction from arbitrary

permutation groups to transitive ones, and from transitive groups to primitive ones.

Now let G be a primitive permutation group on „¦. We say that G is non-basic if

there is an identi¬cation of „¦ with F n for some set F and some positive integer n,

such that the following is true:

each element of G has the form

(a1 , . . . , an ) ’ (a1h g1 , . . . , anh gn ),

where h is a permutation of {1, . . . , n}, and g1 , . . . , gn are permutations

of F.

In other words, G preserves a non-trivial “power structure” on „¦. We say that G

is basic if it is not non-basic.

This de¬nition is similar in structure to that of transitive and primitive groups:

a permutation group is transitive if it preserves no non-trivial subset of „¦, and a

transitive group is primitive if it preserves no non-trivial partition.

Now part of the O™Nan“Scott Theorem is the following assertion:

Theorem 5.7 A basic primitive permutation group is af¬ne, diagonal, or almost

simple.

Here a permutation group is af¬ne if (up to re-labelling the set „¦) it is a sub-

group of the group

{v ’ vA + c : A ∈ GL(V ), c ∈ V }

of permutations of the ¬nite vector space V and contains all the translations v ’

v + c. A diagonal group has a normal subgroup T n , where T is a non-abelian

simple group and n ≥ 2, acting on the set of right cosets of the diagonal subgroup

D = {(t,t, . . . ,t) : t ∈ T }.

Almost simple groups were de¬ned earlier.

Now we consider what kind of information about the ¬nite simple groups is

needed to understand basic permutation groups.

5.5. Modern permutation group theory 43

(a) If G is af¬ne, then G is the semi-direct product of the translation group of V by

an irreducible subgroup H of GL(V ). A similar reduction theorem, due to

Aschbacher, for irreducible linear groups shows that we can further reduce

to the case where the centre Z(H) of H consists of scalar transformations

and H/Z(H) is almost simple. Typically we now require properties about

the irreducible projective representations of almost simple groups.

(b) If G is diagonal, then its properties can usually be derived from routine prop-

erties of simple groups.

(c) In the case where G is almost simple, we need to know about primitive permu-

tation actions (equivalently, maximal subgroups) of almost simple groups.

Many results about primitive permutation groups have been proved by this

method. We restrict ourselves to two applications. The ¬rst application is the

classi¬cation of the 2-transitive groups. In this case, a very simple form of the

O™Nan“Scott theorem (proved originally by Burnside) shows that a 2-transitive

group is either af¬ne or almost simple. We refer to Cameron [4] and Dixon and

Mortimer [13] for the list of 2-transitive groups and for further details of the argu-

ment.

The second, more recent result is a composite theorem about almost simple

primitive groups. The ¬rst part is due to Cameron and Kantor [8], the second to

Liebeck and Shalev [21].

Theorem 5.8 (CFSG) There are absolute constants c1 , c2 with the following prop-

erties. Let G be an almost simple primitive permutation group of degree n. Sup-

pose that G is not one of the following:

(i) a symmetric or alternating group Sm or Am , acting on the set of k-element

subsets of {1, . . . , m} (with n = m );

k

(ii) a symmetric or alternating group Sm or Am , acting on the set of partitions of

{1, . . . , m} into l parts of size k, where kl = m;

(iii) a classical group, acting on an orbit of subspaces of its natural module.

Then

(a) |G| ¤ nc1 ;

(b) G has a base of size at most c2 .

44 Chapter 5. Permutation groups

This theorem is in many ways typical of applications of CFSG to permutation

group theory: a group is either “known” (in some more-or-less precise sense) or

“small”.

We saw that the size of an irredundant base for a permutation group G of

degree n lies between log |G|/ log n and log |G|/ log 2. For primitive groups, Laci

Pyber has conjectured that the lower bound is approximately correct; more specif-

ically, the minimal base size is at most c log |G|/ log n, for some constant c. Part

(b) of the above theorem is a result in the direction of this conjecture.

Exercises

5.1. Show that the number of ways of writing the cycle decomposition of a

permutation g ∈ Sn is equal to the order of the centraliser of g in Sn (the subgroup

of elements commuting with g). Find a formula for this number.

5.2. The Orbit-counting Lemma asserts that the expected value of the number

of ¬xed points of a random element of the permutation group G is equal to the

number of orbits of G. What is the variance of this number?

5.3. Let G be a transitive permutation group on „¦. Let B be a non-empty subset

/

of „¦ with the property that, for all g ∈ G, either Bg = B or B © Bg = 0. Prove that

B is a block of imprimitivity.

5.4. Suppose that |„¦| > 2, and let G be a permutation group on „¦ which pre-

serves no non-trivial equivalence relation. Prove that G is transitive (and hence

primitive).

5.5. Prove Proposition 5.6. Is it true that every block of imprimitivity for a

transitive group G is an orbit of a normal subgroup of G?

5.6. Find a base and strong generating set for the permutation group on the set

{1, 2, 3, 4, 5} generated by s = (1, 2)(4, 5) and t = (2, 3)(4, 5). Hence ¬nd the

order of this group, and determine whether it contains (1, 2, 3)(4, 5).

5.7. Prove that the permutation group G, of degree at least 2, is 2-transitive if and

only if

1

‘ ¬x(g)2 = 2.

|G| g∈G

Generalise.

5.8. Find all systems of imprimitivity for G = S4 acting on the set „¦ of ordered

pairs of distinct elements of {1, 2, 3, 4}. Hence show that the primitive compo-

nents of a transitive group are not uniquely determined.

5.5. Modern permutation group theory 45

5.9. A permutation group G is sharply t-transitive if, given any two ordered t-

tuples of distinct elements of „¦, there is a unique element of G carrying the ¬rst

pair to the second.

Prove that, in a sharply 2-transitive group G, the identity and the ¬xed-point-

free permutations form a normal subgroup N. Show further that N is elementary

abelian, and deduce that the degree of G is a prime power. Deduce that, if t ≥ 2,

then the degree of a sharply t-transitive group is of the form pr + t ’ 2 for some

prime power pr .

Construct a sharply 2-transitive group of degree pr for any prime power pr .

5.10. Prove the following strengthening of Jordan™s Theorem (Corollary 5.4), due

to Cameron and Cohen [6]:

Let G be a transitive permutation group of degree n > 1. Then at least

a proportion 1/n of the elements of G are ¬xed-point-free. Equality

holds if and only if G is sharply 2-transitive.

5.11. Prove that the permutations (1, 2)(3, 4)(5, 6)(7, 8)(9, 10)(11, 12) and

(1, 2, 3)(4, 5, 7)(8, 9, 11) generate a sharply 5-transitive group of degree 12. (This

is the Mathieu group M12 .)

46 Chapter 5. Permutation groups

CHAPTER 6

Cycle index

The cycle index is a polynomial associated with a permutation group. Unlike the

polynomials we considered earlier for codes and matroid, it has many variables

(possibly as many as the degree of the permutation group). To clarify the process

of substituting into a multivariate polynomial F in indeterminates s1 , . . . , sn , we

use the notation

F(si ← ti )

for the result of substituting the term ti for si for i = 1, . . . , n.

The cycle index is basic in the theory of combinatorial enumeration pioneered

by Red¬eld and P´ lya. We refer to Harary and Palmer [18] for a more detailed

o

account.

6.1 De¬nition

Let G be a permutation group on a set „¦, where |„¦| = n. For each element

g ∈ G, we can decompose the permutation g into a product of disjoint cycles; let

ci (g) be the number of i-cycles occurring in this decomposition. Now the cycle

index of G is the polynomial Z(G) in indeterminates s1 , . . . , sn given by

1

‘ s11 · · · snn .

c (g) c (g)

Z(G) =

|G| g∈G

This can be regarded as a multivariate probability generating function for the cycle

structure of a random element of G (chosen from the uniform distribution). In

particular,

PG (x) = Z(G)(s1 ← x, si ← 1 for i > 1)

47

48 Chapter 6. Cycle index

is the probability generating function for the number of ¬xed points of a random

element of G, so that substituting x ← 0 gives the proportion of derangements

in G. In other words,

1

‘ xc1(g).

PG (x) =

|G| g∈G

The number c1 (g) is the number of ¬xed points of g, which we called ¬x(g)

in Chapter 5; the function g ’ c1 (g) is the permutation characterof G.

Let us work two examples. First, let G be the symmetric group of degree 4.

Each partition of 4 is the cycle type of some element of G, and it is not hard to

count the number of elements corresponding to each partition:

Partition 4 31 22 211 1111

Number 6 8 3 6 1

So

1

(6s4 + 8s1 s3 + 3s2 + 6s2 s2 + s4 ).

Z(G) = 2 1 1

24

Now let us take the same group S4 acting on the set of 2-element subsets

of {1, 2, 3, 4}. We simply need to ¬nd for each shape of permutation the cycle

structure on the set of pairs; we obtain the following:

On points 4 31 22 211 1111

On pairs 42 33 2211 2211 111111

So

1

(6s2 s4 + 8s2 + 9s2 s2 + s6 ).

Z(G) = 3 12 1

24

6.2 The cycle index theorem

The cycle index is an important tool in combinatorial enumeration. Typically,

we have a collection of “¬gures” decorating some set (e.g. colours of the faces of

a regular polyhedron), and we are interested in counting the number of con¬gura-

tions up to some notion of symmetry (given by a group of automorphisms of the

set). More formally, let A be a set of “¬gures”, each of which has a non-negative

integer “weight”. The number of ¬gures may be in¬nite, but we assume that there

are only ¬nitely many ¬gures of any given weight. The ¬gure-counting series of

A is the formal power series

‘ ant n,

A(t) =

n≥0

where an is the number of ¬gures of weight n; that is, it is just the generating

function for ¬gures by weight.

6.2. The cycle index theorem 49

Now let „¦ be a ¬nite set. A function f : „¦ ’ A has a weight given by

‘ wt( f (±)).

wt( f ) =

±∈„¦

If G is a permutation group on „¦, then there is a natural action of G on the set of

functions, given by the rule

f g (±) = f (±g’1 ).

(The inverse is required to make this a good de¬nition of an action.) Clearly

this action preserves the weight of a function. The function-counting series is the

formal power series

B(t) = ‘ bnt n ,

n≥0

where bn is the number of G-orbits on the set of functions of weight n. Now the

Cycle Index Theorem states:

Theorem 6.1 With the above notation,

B(t) = Z(G; si ← A(t i )).

Proof Here is a sketch of the proof: ¬ll in the details as an exercise.

The generating function for all functions, disregarding the group action, is

A(t)n , since the coef¬cient of t m in A(t)n is equal to the sum of ai1 · · · ain over all

expressions i1 + · · · + in = m. Note that A(t)n = sn (s1 ← A(t)), and sn is the cycle

1 1

index of the trivial group.

c (g) c (g)

For any permutation g, let z(g) = s11 · · · snn . A function is ¬xed by the

permutation g if and only if it is constant on each cycle in the cycle decomposition

of g. The weight of such a function is the sum of the products of cycle length and

weight of the ¬gure at a point of the cycle. Hence the generating function for the

number of functions ¬xed by g is

A(t)c1 (g) · · · A(t n )cn (g) = z(g; si ← A(t i )).

Now the result follows from the Orbit-Counting Lemma (Theorem 5.3) and

the de¬nition of cycle index, on averaging over G.

Here is a typical application of the theorem. How many graphs are there on 4

vertices with any given number (from 0 to 6) of edges, up to isomorphism? We

take „¦ to be the set of all 2-elements of the vertex set {1, 2, 3, 4}. To each element

{i, j} of „¦ we attach either an edge or a non-edge. Taking edges to have weight 1

and non-edges to have weight 0, the weight of the function is just the total number

50 Chapter 6. Cycle index

of edges in the corresponding graph. Moreover, two graphs are isomorphic if

and only if there is a permutation of {1, 2, 3, 4} carrying the ¬rst function to the

second. So, taking the ¬gure-counting series to be A(t) = 1 + t, and the group

S4 acting on 2-sets (whose cycle index we calculated in the previous section), we

¬nd the generating function for graphs on four vertices (enumerated by edges) to

be

1

(6(1 + t 2 )(1 + t 4 ) + 8(1 + t 3 )2 + 9(1 + t)2 (1 + t 2 )2 + (1 + t)6 )

24

= 1 + t + 2t 2 + 3t 3 + 2t 4 + t 5 + t 6 .

6.3 Some other counting results

Let G be a permutation group on a set „¦. Many counting problems related

to G, other than those described in the Cycle Index Theorem, can be solved by

specialisations of the cycle index. Here are some examples.

(a) Let Fn be the number of orbits of G acting on the set of all n-tuples of distinct

elements of „¦. We consider the exponential generating function

Fnt n

FG (t) = ‘

n≥0 n!

for the sequence (Fn ). Now we have

FG (t) = Z(G)(s1 ← x + 1, si ← 1 for i > 1).

(b) If instead we want the total number Fn— of orbits of G on n-tuples (with repeats

allowed), then it can be calculated as

n

‘ S(n, k)Fk ,

Fn— =

k=1

where S(n, k) is the Stirling number of the second kind, the number of par-

titions of an n-element set into k parts.

(c) Let fn be the number of orbits of G acting on the set of all n-element subsets

of „¦. Then the ordinary generating function

‘ f nt n

fG (t) =

n≥0

is given by the specialisation

fG (t) = Z(G)(si ← t i + 1).

6.4. The Shift Theorem 51

(d) The Parker vector of G is the vector (p1 , p2 , . . .), where pk is the number of

orbits of G on the set of k-cycles occurring in the cycle decompositions of its

elements (and G acts on these k-cycles by conjugation). The Parker vector

was introduced by Parker in the context of computational Galois theory, and

was studied by Gewurz [14]. It is given by

pk = k[(‚/‚sk )Z(G)](si ← 1).

Many of these sequences play an important role in combinatorial enumeration.

See [3] for more details about (a)“(c).

6.4 The Shift Theorem

Let G be a permutation group on „¦. For any subset ∆ of „¦, we de¬ned G[∆]

to be the group of permutations of ∆ induced by elements of G ¬xing ∆ pointwise.

Thus, G[∆] is the quotient of the setwise stabiliser of ∆ by its pointwise stabiliser.

We let P „¦/G denote the set of G-orbits on the power set of „¦; by abuse of

notation, this will also be used for a set of orbit representatives.

Now the following result (the Shift Theorem) holds:

Theorem 6.2 For any ¬nite permutation group G on „¦,

‘ Z(G[∆]) = Z(G; si ← si + 1).

∆∈P „¦/G

Proof Rather than a proof of this theorem (which is just elementary but compli-

cated double counting), I will try to explain why it has to hold. (This explana-

tion would be a proof if we knew that the cycle index is the unique polynomial

for which the Cycle Index Theorem holds.) Suppose that we have a set A— of

¬gures containing one distinguished ¬gure — of weight zero. Let A— (t) be its

¬gure-counting series, and A(t) the ¬gure-counting series of A = A— \ {—}. Then

A(t) = A— (t) ’ 1, and so the function-counting series is

B(t) = Z(G; si ← A(t i ) + 1).

Now this can be calculated in another way. Any function f is determined by

giving the set ∆ = {± ∈ „¦ : f (±) = —} and then the function f : ∆ ’ A given by

its restriction to ∆. Two functions lie in the same orbit of G if and only if

(a) the sets ∆ lie in the same orbit of G; and

52 Chapter 6. Cycle index

(b) assuming that we have translated by an element of G to make these two sets

equal, the functions f lie in the same orbit of G[∆].

So the function-counting series is given by

‘ Z(G[∆], si ← A(t i )).

B(t) =

∆∈P „¦/G

So the two polynomials in the theorem yield the same result for every substitution

si ← A(t i ), for any ¬gure-counting series A(t).

This theorem may not seem to have very much use as it stands. One use to

which it was put in [3] was to extend the de¬nition of cycle index to certain in¬-

nite permutation groups, namely, those which are oligomorphic. (A permutation

group is said to be oligomorphic if the number fn of orbits on n-element subsets

is ¬nite for all natural numbers n.) The point is that the cycle index of an in¬nite

permutation group cannot be de¬ned directly, since permutations may have in-

¬nitely many cycles of some length; but the right-hand side of the Shift Theorem

is well-de¬ned for any oligomorphic group, if we interpret P „¦/G to be a set of

representatives for the orbits on ¬nite sets.

Our interest in the theorem is a bit different. A corollary of it is the follow-

ing result, ¬rst observed by Boston et al. [2]. Recall that PG (x) is the probability

generating function for ¬xed points of random elements of G, while FG (t) is the

exponential generating function for the number of orbits of G on n-tuples of dis-

tinct elements.

Corollary 6.3 For any ¬nite permutation group G, we have

FG (t) = PG (t + 1).

Proof We know that

PG (x) = Z(G; s1 ← x, si ← 1 for i > 1).

Also, a set ∆ of cardinality n can be labelled in n! different ways; these fall into

n!/|G(∆)| orbits under G. So we have

n! t n

FG (t) = ‘ ‘

n≥0 ∆∈P „¦/G,|∆|=n |G(∆)| n!

‘ Z(G(∆), s1 ← t, si ← 0 for i > 1)

=

∆∈P „¦/G

= Z(G; s1 ← t + 1, si ← 1 for i > 1),

6.4. The Shift Theorem 53

the last equality coming from the Shift Theorem. So the result holds.

However, the original proof by Boston et al. [2] is more direct. Let c1 (g)

denote the number of ¬xed points of the element g. Then the number of ordered

j-tuples of distinct elements it ¬xes is

c1 (g)(c1 (g) ’ 1) · · · (c1 (g) ’ j + 1).

By the Orbit-Counting Lemma,

1

‘ c1(g)(c1(g) ’ 1) · · · (c1(g) ’ j + 1).

Fj =

|G| g∈G

Multiplying by t j / j! and reversing the order of summation,

n

c1 (g)

1

‘ ‘ j tj

FG (t) =

|G| g∈G j=0

1

‘ (t + 1)c1(g)

=

|G| g∈G

= PG (t + 1),

since PG (x) = ‘g∈G xc1 (g) /|G|.

Exercises

6.1. Let g be a permutation of „¦, and suppose that the order of g is m. Show that

¬x(gk ) = ‘ lsl (g)

l|k

for all k dividing m, and deduce that

1

‘ µ(k/l) ¬x(gl )

sk (g) =

k l|k

for all k dividing m, where µ is the M¨ bius function.

o

6.2. Let G be a permutation group on two sets „¦1 and „¦1 . Let ¬x1 (g) and ¬x2 (g)

denote the numbers of ¬xed points of G in „¦1 and „¦2 respectively. Suppose that

¬x1 (g) = ¬x2 (g) for all g ∈ G. Prove that the cycle indices of the two permutation

groups G„¦1 and G„¦2 are equal. (Hint: use the preceding exercise.)

6.3. Let G be the group of rotations of a cube.

(a) Prove that G is isomorphic to the symmetric group S4 .

54 Chapter 6. Cycle index

(b) Compute the cycle index of G, acting on the set of faces of the cube.

(c) Is this action of G isomorphic to the action of S4 on the set of 2-element

subsets of {1, . . . , 4}?

6.4. Find the generating function for colourings of the faces of the cube red and

blue, enumerated by the number of red faces.

6.5. Use the Cycle Index Theorem to enumerate

(a) graphs on four vertices having at most one loop at each vertex but no multiple

edges, by number of edges;

(b) graphs on four vertices having at most two edges between each pair of distinct

vertices but no loops, by number of edges.

6.6. Verify the Shift Theorem for the permutation group S4 (in its natural action

on four points).

6.7. Use the Corollary to the Shift Theorem to calulcate the function PG (x),

where G is the symmetric group Sn . Deduce that the probability that a random

permutation has no ¬xed points tends to 1/e as n ’ ∞.

6.8. Prove that

∞

si

‘ Z(Sn) = exp ‘ .

i=1 i

n≥0

CHAPTER 7

Codes and permutation groups

This chapter describes the link between codes and permutation groups. From any

linear code, we construct a permutation group, whose cycle index is essentially the

weight enumerator of the code. If we start instead with a Z4 -linear code, the cycle

index of the group is the symmetrised weight enumerator of the code. Essentially,

we “in¬‚ate” each coordinate of the code into a copy of the alphabet.

We begin with a technical result concerning a similar operation of “in¬‚ating”

a matroid, which will be relevant in Chapter 8.

7.1 In¬‚ating a matroid

How does the Tutte polynomial of a matroid change if a single element is re-

placed by q parallel elements? This can be described explicitly in terms of the

Tutte polynomials of the deletion and contraction with respect to that element.

However, we need to know what happens if every element of the matroid is re-

placed by a set of q parallel elements, and here the answer is much simpler.

To be more precise, we de¬ne the q-fold in¬‚ation of a matroid M on the set E

to be the matroid on the set E — Q, where Q is a q-element set, whose independent

sets are as follows: for each independent set A ⊆ E, and each function f : A ’

Q, the set {(a, f (a)) : a ∈ A} of E — Q is independent; and these are the only

independent sets.

55

56 Chapter 7. Codes and permutation groups

Proposition 7.1 If Mq is a q-fold in¬‚ation of M, then

ρ(E)

yq ’ 1 xy ’ x ’ y + yq q

T (Mq ; x, y) = ,y .

T M;

yq ’ 1

y’1

Proof To each subset A ⊆ E, there are 2q ’ 1 subsets of E — Q whose projection

onto E is A. For any such subset, the rank (in Mq ) is equal to the rank of A in Q.

The contribution to the Tutte polynomial from such sets is given by

|A| q

q

∏‘

ρE’ρA |A|’ρA

(y ’ 1) j’1

(x ’ 1) (y ’ 1)

j

i=1 j=1

= (x ’ 1)ρE’ρA (y ’ 1)|A|’ρA (yq ’ 1)|A|

ρA

yq ’ 1

= (x ’ 1)ρE’ρA (yq ’ 1)|A|’ρA

y’1

ρ(E) ρE’ρA

yq ’ 1 (x ’ 1)(y ’ 1)

(yq ’ 1)|A|’ρA .

=

yq ’ 1

y’1

Summing over A ⊆ E, we obtain

ρE ρE’ρA

yq ’ 1 (x ’ 1)(y ’ 1)

‘ (yq ’ 1)|A|’ρA

T (Mq ; x, y) =

yq ’ 1

y’1 A⊆E

ρE

yq ’ 1 (x ’ 1)(y ’ 1)

+ 1, yq .

= T M; q ’1

y’1 y

7.2 The connection

Let C be a linear [n, k] code over GF(q). We construct from C a permutation

group whose cycle index is (more-or-less) the weight enumerator of C.

The group we construct is the additive group of C. We let it act on the set

{1, . . . , n} — GF(q) (a set of cardinality nq) in the following way: the codeword

(a1 , . . . , an ) acts as the permutation

(i, x) ’ (i, x + ai )

of the set {1, . . . , n} — GF(q). The group G(C) is an elementary abelian group of

order qk .

1

WC (X,Y ) = Z(G; s1 ← X 1/q , s p ← Y p/q ), where q is a power

Proposition 7.2

|C|

of the prime number p.

7.3. More generally . . . 57

Proof Consider the group element w = (a1 , . . . , an ). If ai = 0, then the q points

of the form (i, x) for x ∈ GF(q) are all ¬xed by this element; if i = 0, they are

permuted in q/p cycles of length p, each of the form

(i, x) ’ (i, x + a1 ) ’ (i, x + 2ai ) ’ · · · ’ (i, x + pai ) = (i, x),

the last equation holding because GF(q) has characteristic p. So this element

q(n’wt(w)) (q/p) wt(w)

contributes s1 sp to the sum in the formula for the cycle index,

and X n’wt(w)Y wt(w) to the weight enumerator of C. The result follows.

7.3 More generally . . .

The construction of a permutation group from a code does not require the code

to be linear, only for it to form an additive group. So the procedure works much

more generally. What is the coding-theoretic equivalent of the cycle index of the

group?

Proposition 7.3 Let C be an additive Z4 -code, with symmetrised weight enumer-

ator SC . Then

1

SC (X,Y, Z) = Z(G; s1 ← X 1/4 , s2 ← Y 1/2 , s4 ← Z).

|C|

Proof The proof is almost identical to that of Proposition 7.2. The permutation

corresponding to the codeword w = (a1 , . . . , an ) acts on the set {(i, x) : x ∈ Z4 } as

four ¬xed points if ai = 0; as two 2-cycles if ai = 2; or as one 4-cycle if ai = 1 or

ai = 3.

More generally, let C be any subgroup of the direct product A1 — A2 — · · · — An ,

where A1 , . . . , An are groups of order q. Then C acts on the set n Ai (disjoint

i=1

union) in the obvious way. The cycle index of the corresponding permutation

group is a kind of generalised symmetrised weight enumerator of C, a multivariate

polynomial which counts the number of codewords whose projection onto Ai has

order mi , where m1 , . . . , mn are divisors of q. I will not pursue this further.

Exercises

7.1. Calculate the Tutte polynomial of a q-fold expansion of the free matroid Fr

and of its dual, and show that both of these matroids are graphic.

Remark The dual of the above matroid was used recently by Alan Sokal [29]

to show that the zeros of chromatic polynomials of planar graphs are dense in the

complex plane outside the circle with centre and radius 1.

58 Chapter 7. Codes and permutation groups

7.2. True or false? A permutation group with cycle index involving only s1 and

s2 arises as G(C) for some linear code over a ¬eld of characteristic 2.

7.3. Let G be an abelian permutation group, having n orbits each of length q.

Show that G i associated with a code of length n over alphabets A1 , . . . , An , each

of which is an abelian group of order q.

7.4. Let (vi : i ∈ I) be vectors spanning a vector space V over F = GF(q). Ver-

ify the following description of the group of the code associated with the vector

matroid de¬ned by these vectors:

• the domain is „¦ = I — F;

• the group is V — ;

• the action is given by

f : (i, a) = (i, a + vi f )

for i ∈ I, a ∈ F and f ∈ V — .

CHAPTER 8

IBIS groups

In this chapter, we consider a special class of permutation groups introduced by

Cameron and Fon-Der-Flaass [7], which have a very close connection with ma-

troids, in the sense that the bases for the permutation group form the bases of

a matroid. These include the groups we associated with linear codes, for which

the weight enumerator of the code is essentially the same as the cycle index of

the group. They also include the base-transitive groups, for which the associated

matroids are perfect matroid designs. We conclude by proposing a more general

polynomial which includes both Tutte polynomial and cycle index.

This is surely not the end of the story. For an arbitrary permutation group,

the irredundant bases do not constitute a matroid. Perhaps there is some more

general structure, for which the analogue of the Tutte polynomial of a matroid can

be de¬ned.

This chapter is my reason for preparing these notes. The original version is in

the paper [5].

8.1 Matroids and IBIS families

The basic idea which connects matroids to permutation groups works in much

greater generality.

Let I be an index set, and let (Xi : i ∈ I) be a family of subsets of a set A. For

any J ⊆ I, let

XJ = X j.

j∈J

By convention, we put X0 = A.

/

59

60 Chapter 8. IBIS groups

The subset J of I is called a base if XJ = XI . Moreover, if J is ordered, say

J = ( j1 , . . . , jk ), then we say that J is irredundant if, for each m with 1 ¤ k, we

have

X jm ⊇ X{ j1 ,..., jm’1 } ,

or, in other words, X{ j1 ,..., jm } ‚ X{ j1 ,..., jm’1 } . Note that any ordered base can be

made irredundant by dropping those indices for which this condition fails.

Theorem 8.1 The following conditions on a family (Xi : i ∈ I) of sets are equiva-

lent:

(a) All irredundant bases have the same number of elements.

(b) The irredundant bases are preserved by re-ordering.

(c) The irredundant bases are the bases of a matroid on I.

Proof Suppose that condition (a) holds, and let J be an (ordered) irredundant

base and J be obtained by re-ordering J. Clearly J is a base, so we can obtain an

irredundant base by possibly dropping some elements. But, if any elements are

dropped, then the resulting base would be smaller than J. So (b) holds.

Next, suppose that (b) holds. We have to verify the matroid base axioms, that

is, no base contains another, and the exchange axiom holds. The ¬rst condition

is clear: if J ‚ K, we can order K so that the elements of J come ¬rst; then the

irredundance of K is contradicted.

Let J and K be irredundant bases, and suppose that j ∈ J \ K. Order J ∪ K \ { j}

so that the elements of J \ { j} come ¬rst. This is a base, and so we can obtain an

irredundant base by dropping some elements of K. We have to show that only

one element of K remains; so suppose not, and let k be the ¬rst element of K to

appear. Then the ordered sequence consisting of the elements of J \ { j}, then k,

then j is an irredundant base, but if the last two elements are swapped, it is no

longer irredundant, contradicting (b).

Finally, (c) trivially implies (a).

A family of sets satisfying the conditions of this theorem is called an IBIS fam-

ily. (This term is an acronym for “Irredundant Bases of Invariant Size”, re¬‚ecting

condition (a).)

Every matroid can be represented by an IBIS family. For let M be a matroid

on E, and let A be the family of hyperplanes of M. For e ∈ E, let Xe be the set of

hyperplanes containing e. It is now a simple exercise to prove that (Xe : e ∈ E) is

an IBIS family, whose associated matroid is M. This is a bit surprising: we think

of the exchange axiom as an essential part of the de¬nition of a matroid; but here

we see that it follows from the constancy of base size.

8.2. IBIS groups 61

8.2 IBIS groups

Let G be a permutation group on „¦, We say that G is an IBIS permutation

group, or IBIS group for short, if the family (G± : ± ∈ „¦) of point stabilisers is an

IBIS family of subsets of G.

Remark The family of point stabilisers in a permutation group is closed under

conjugation. Conversely, if (Gi : i ∈ I) is any IBIS family of subgroups of the

group G which is closed under conjugation, then GI is a normal subgroup of G

and G/GI is isomorphic to an IBIS permutation group. I do not know anything

about IBIS families of subgroups which are not closed under conjugation.

In the case when G is a permutation group on „¦ and (G± : ± ∈ „¦) is the family

of point stabilisers, we see that GI is just the pointwise stabiliser of I, for I ⊆ „¦.

Hence the notions of a base and an irredundant base for the family coincide with

those we met in Chapter 5: a base is a sequence of points whose stabiliser is the

identity, and it is irredundant if no point in the sequence is ¬xed by the stabiliser

of its predecessors.

So we can say more succinctly: the permutation group G on „¦ is an IBIS

group if its irredundant bases all have the same cardinality. The irredundant bases

of such a group G are the bases of a matroid on the set „¦, and clearly G acts as

a group of automorphisms of this matroid. We de¬ne the rank of an IBIS group

to be the common cardinality of its irredundant bases (that is, the rank of the

associated matroid).

We now give some examples of IBIS groups. First we note that adding or re-

moving global ¬xed points of a permutation group doesn™t change the IBIS prop-

erty or the rank; so, where necessary, we assume that there are none. (A global

¬xed point of an IBIS group is a loop of the associated matroid.)

Any non-identity semiregular permutation group (one in which the stabiliser

of any point is the identity) is an IBIS group of rank 1, and conversely (apart

from global ¬xed points). Also, the stabiliser of a point in an IBIS group is an

IBIS group, with rank one less than that of the original. (This is the analogue of

deletion for IBIS groups. There is no natural analogue of contraction.)

Let t be a non-negative integer, and let G be a t-transitive permutation group in

which the stabiliser of any t + 1 points is the identity (but the stabiliser of t points

is not the identity. Such groups have had a lot of attention in the literature, though

there appears to be no general name for them. I will call them t-Frobenius groups:

this extends the terminology Frobenius groups for permutation groups satisfying

this condition with t = 1. (A 0-Frobenius group is just a semiregular permutation

group.)

Any t-Frobenius group is an IBIS group, and the associated matroid is the

uniform matroid Ut+1,n . The converse is also true:

62 Chapter 8. IBIS groups

Theorem 8.2 Let G be an IBIS group of rank t + 1, whose associated matroid is

the uniform matroid Ut+1,n . Then G is a t-Frobenius group.

Proof We have to show that such a group is t-transitive. The proof is by induction

on t. When t = 0, there is nothing to show; we start the induction with the case

t = 1. An exercise in Wielandt™s book [32] shows that, if G is a permutation group

in which all 2-point stabilisers are trivial, then either G is semiregular, or G has

one orbit on which it acts s a Frobenius group, and the action on all other orbits

is regular. In our case, there cannot be any regular orbits, since these would give

bases of cardinality 1. So G is a Frobenius group.

Now suppose that the result holds for t ’ 1, and let G be an IBIS group of

rank t + 1 with associated matroid Ut+1,n . Then the point stabiliser G± acts on

the remaining points as an IBIS group with matroid Ut,n’1 . By induction, G± is

(t ’ 1)-transitive; so G is t-transitive, as required.

For Frobenius groups, we have good information about the structure, based on

Frobenius™ Theorem:

Theorem 8.3 Let G be a Frobenius group. Then the identity and the ¬xed-point-

free elements form a subgroup N of G, which is regular and normal in G.

The subgroup N is called the Frobenius kernel of G. It follows that G is the

semidirect product of N and a point stabiliser G± (which is called a Frobenius

complement). Moreover, Thompson proved that the Frobenius kernel is nilpo-

tent, and Zassenhaus proved that the structure of a Frobenius complement is very

restricted: in particular, it has at most one non-abelian composition factor (this

being isomorphic to the smallest non-abelian simple group A5 ). See Passman [26]

for an account of this work (which preceded CFSG).

A 2-Frobenius group is usually called a Zassenhaus group. These groups were

completely determined by Zasenhaus, Feit, Ito, and Suzuki (also before CFSG);

such a group either is soluble or has minimal normal subgroup isomorphic to

PSL(2, q) or Sz(q) for some prime power q. (The Suzuki groups Sz(q) were dis-

covered by Suzuki in the course of this determination.) An account of this is

also found in Passman [26]. From this, it is possible to determine the t-Frobenius

groups for all larger values of t.

Hence we can conclude that all IBIS groups whose associated matroid is Ur,n

for r > 2 are known. However, the situation is very different for matroids which

are in¬‚ations of uniform matroids (see Exercise 8.7 and the following remark);

so the standard procedure in matroid theory of collapsing parallel elements to a

single element cannot be applied here.

8.3. Groups from codes 63

Let V be a vector space of dimension n over the ¬eld GF(q). The general

linear group GL(n, q) acts on V as an IBIS group; the associated matroid is the

complete vector matroid V (n, q). To see this, we observe ¬rst that the pointwise

stabiliser of any set of vectors ¬xes pointwise the subspace they span; and then,

given any proper subspace, there is a non-identity linear transformation ¬xing this

subspace pointwise.

Any subgroup of GL(n, q) with this last property is an IBIS group with the

same associated matroid. One example is the symplectic group, the group of

linear transformations preserving a non-degenerate alternating bilinear form B on

V . For any hyperplane has the form a⊥ = {v ∈ V : B(a, v) = 0} for some non-zero

vector a; this hyperplane is ¬xed pointwise by the symplectic transvection

x ’ x + B(x, a)a.

The group we associated with a linear code in the last chapter is an IBIS group.

We discuss this in the next section.

The 5-transitive Mathieu group M24 is an IBIS group of rank 7. The associated

matroid is not the familiar one whose hyperplanes are the blocks of the associated

Steiner triple system S(5, 8, 24) de¬ned in Exercise 3.4 (this matroid has rank 6),

nor is it the matroid associated with the extended Golay code mentioned in Chap-

ter 1 (this matroid has rank 12).

8.3 Groups from codes

Let G(C) be the permutation group that we associated earlier to a [n, k] code

C over GF(q). Recall that G(C) is the additive group of C, and acts on the set

{1, . . . , n} — GF(q) by the rule

(a1 , . . . , an ) : (i, x) ’ (i, x + ai ).

This group is an IBIS group of rank k. For a set {(i1 , x1 ), . . . , (ik , xk )} is a base for

G(C) if and only if the only codeword with zeros in positions i1 , . . . , ik is the zero

word; this is equivalent to saying that the columns of a generator matrix of C with

indices i1 , . . . , ik are linearly independent; so any irredundant base for G(C) has

rank k.

Now the matroid associated with C has the property that a set {i1 , . . . , il } is

independent if and only if the corresponding columns of a generator matrix for

C are linearly independent. Thus the matroid associated with G(C) is the q-fold

in¬‚ation of the matroid M(C) of the code C.

Proposition 7.1 shows that we can pass between T (M(C)) and T (M(C)q ).

Greene™s theorem shows that these polynomials determine the weight enumerator

64 Chapter 8. IBIS groups

of C, and hence the cycle index of G. But the weight enumerator of C does not

determine the Tutte polynomial of M(C), since we can have codes with the same

weight enumerator but different Tutte polynomials.

So in this case, the Tutte polynomial carries more information than the cycle

index. Sometimes, however, it is the other way around, as we will see.

8.4 Flat actions

The action of an IBIS group on its associated matroid has the following very

strong property:

(—) The pointwise stabiliser of any set of points ¬xes pointwise the ¬‚at spanned

by the set.

For let B be a subset of A minimal with respect to having the same pointwise

stabiliser. A point ± not ¬xed by the stabiliser of B can be adjoined to B, and the

result extended to an irredundant base; so ± is independent of B.

An action of a group on a matroid will be called ¬‚at if condition (—) holds.

Any permutation group has a ¬‚at action on the free matroid; and any linear

group (that is, any subgroup of GL(n, q)) has a ¬‚at action on the vector matroid

V (n, q).

If a group has a ¬‚at action on a perfect matroid design, then an analogue of

the Shift Theorem holds: there is a linear relation between the numbers of orbits

of the group on independent tuples of points and the probabilities that a random

group element has a ¬‚at of given rank as its ¬xed point set. We prove this by

showing that a linear relation holds between numbers of orbits on independent

tuples and numbers of orbits on arbitrary tuples; then we can invoke the original

Shift Theorem corollary.

Theorem 8.4 Let M be a PMD(k0 , . . . , kr ), with kr = n. Then there are numbers

b(m, i), for 0 ¤ m ¤ n and 0 ¤ i ¤ r, depending only on k0 , . . . , kr , such that

the following is true: If a group G has a ¬‚at action on M and has xi orbits on

independent i-tuples and ym orbits on m-tuples of distinct elements, then

r

ym = ‘ b(m, i)xi

i=0

for m = 0, . . . , n.

Proof By the Orbit-Counting Lemma, it suf¬ces to show that such a linear re-

lation holds between the number of linearly independent i-tuples ¬xed by an ar-

bitrary element g ∈ G and the total number of m-tuples of distinct elements ¬xed

8.4. Flat actions 65

by g. Since the ¬xed points of G form a ¬‚at, it suf¬ces to establish such a relation

between the numbers of tuples in any ¬‚at of M.

So let F be an s-¬‚at containing xi independent i-tuples and ym m-tuples of

distinct elements. Then

i’1

∏ (ks ’ k j ) = Xi(ks),

xi =

j=0

m’1

∏ (ks ’ t) = Ym(ks),

ym =

t=0

where Xi and Yi are polynomials of degree i, independent of s. It follows immedi-

ately that the theorem holds for m ¤ r, with (b(m, i)) the transition matrix between

the two sequences of polynomials.

For m > r, let Fm (x) be the unique monic polynomial of degree m having

roots k0 , . . . , kr and no term in xl for r + 1 ¤ l ¤ m ’ 1. Using Fm , we can ex-

press kim (and hence Ym (ki )) as a linear combination of 1, ki , . . . , kir (and hence of

X0 (ki ), . . . , Xr (ki )). This concludes the proof.

Remark It is also interesting to consider the numbers zm of orbits of G on arbi-

trary m-tuples. As we mentioned in Section 6.3, for any permutation group G, we

have

m

‘ S(m, k)yk ,

zm =

k=1

where the numbers S(m, k) are the Stirling numbers of the second kind (so that

S(m, k) is the number of partitions of an m-set with k parts). Hence, by the standard

inversion for the Stirling numbers, we have

m

‘ s(m, k)zk ,

ym =

k=1

where the numbers s(m, k) are the (signed) Stirling numbers of the ¬rst kind (so

that (’1)m’k s(m, k) is the number of permutations of an m-set having k cycles).

Thus we can easily move back and forth between these two sequences.

In the case of the free matroid, every set is independent, and so xi = yi , and the

matrix (b(m, i)) is the identity.

For the complete vector matroid V (n, q), we have

m

m

zm = ‘ xi ,

i q

i=0

where the numbers m q are the Gaussian coef¬cients, so that m q is the number

i i

of i-¬‚ats in V (m, q). Hence the matrix (b(m, i)) is the composite of the matrices

of Gaussian coef¬cients and Stirling numbers.

66 Chapter 8. IBIS groups

All this can be found in Cameron and Taylor [10].

Remark The exponential generating function for y0 , . . . , yn is PG (x + 1), by the

corollary to the Shift Theorem. So the numbers x0 , . . . , xr determine PG (x).

Now the number of ¬xed points of an element of G is equal to the cardinality

of a ¬‚at, that is, in the set {k1 , . . . , kr }; so the other coef¬cients of PG (x) are all

zero. If the coef¬cient of xki in PG (x) is pi , then we have a linear map connecting

the sequences (p0 , . . . , pr ) and (x0 , . . . , xr ).

In the case of the free matroid, this map is given by Corollary 6.3: we have

xi /i! = ‘ij=0 ij p j . In the case of the complete vector matroid, it is the q-analogue

of this, involving the Gaussian coef¬cients. In each case there is a standard method

to invert the matrix. (See Cameron and Majid [9] for a connection between inver-

sion of the q-analogue and af¬ne braided groups.)

I do not know a convenient formula for this matrix or its inverse in the case of

a general PMD.

8.5 Base-transitive groups

If G is a permutation group which permutes its ordered (irredundant) bases

transitively, then clearly all the irredundant bases have the same size, and so G is

an IBIS group. Moreover, since G also permutes the ordered independent sets of

size i transitively for all i, the associated matroid is a perfect matroid design.

Such groups have been given the somewhat unfortunate name of “geomet-

ric groups”. Here I will simply call them base-transitive permutation groups,

or base-transitive groups for short. The base-transitive groups of rank greater

than 1 were determined by Maund [23], using CFSG; those of suf¬ciently large

rank by Zil™ber [33] by geometric methods not requiring the Classi¬cation. Base-

transitive groups of rank 1 are just regular permutation groups (possibly with some

global ¬xed points).

Theorem 8.5 For a base-transitive group G, the p.g.f. PG (x) and the Tutte poly-

nomial of the associated matroid determine each other, and each is determined by

knowledge of the numbers of ¬xed points of elements of G.

Proof A permutation group G is base-transitive if and only if the stabiliser of

any sequence of points acts transitively on the points that it doesn™t ¬x (if any).

Thus the ¬xed points of every element form a ¬‚at. Also, by Corollary 5.4, every

¬‚at is the ¬xed point set of some element. So the numbers of ¬xed points of the

elements of G determine the cardinalities of ¬‚ats, and hence the Tutte polynomial

of the matroid, by Theorem 3.6.

8.6. Some examples 67

Theorem 8.4 shows that the numbers k0 , . . . , kr of ¬xed points of elements in

a base-transitive group determine the function PG (x), since the numbers x0 , . . . , xr

are all equal to 1.

To obtain PG (x) directly from the Tutte polynomial, we show the following:

n r

a(m, i)

‘‘ xm ,

PG (x + 1) =

i=0 R(i)

m=0

where n = kr is the number of points, and R(i) is the number of independent i-

tuples in the matroid; as in Theorem 3.6, a(m, i) is the number of m-sets of rank i.

To prove this, we note that each m-set can be ordered in m! different ways. If

the rank of the m-set is i, the resulting sequence has stabiliser of order ∏r’1 (n ’

j=i

k j ), and so lies in an orbit of size ∏ j=0 (n ’ k j ) = R(i). Thus, the number of orbits

i’1

on such tuples is a(m, i)m!/R(i). We obtain the total number of orbits on m-tuples

by summing over i, and so we ¬nd that the exponential generating function is

the right-hand side of the displayed equation. But this e.g.f. is PG (x + 1), by the

corollary to the Shift Theorem.

Even for a regular permutation group, knowledge of the ¬xed point numbers

does not determine the cycle index; the latter also contains information about the

number of group elements of each given order. A regular permutation group is

base-transitive. So we see that the cycle index contains more information than the

Tutte polynomial in this case.

8.6 Some examples

Unfortunately, the cycle index does not in general tell us whether a permu-

tation group is base-transitive. The simplest counterexample consists of the two

permutation groups of degree 6,

G1 = (1, 2)(3, 4), (1, 3)(2, 4) , G2 = (1, 2)(3, 4), (1, 2)(5, 6) .

The ¬rst is base-transitive; the second is an IBIS group of rank 2 (indeed, it is

the group arising from the binary even-weight code of length 3), but not base-

transitive. A simple modi¬cation of this example shows that the cycle index does

not determine whether the IBIS property holds.

Suppose we are given the cycle index of one of these groups, namely Z(G) =

16 16

22 2

4 (s1 + 3s1 s2 ), or simply the p.g.f. for ¬xed points, namely PG (x) = 4 (x + 3x ).

(a) If we are told that the group is base-transitive, then we know that its matroid

is a PMD(2, 6), and so we can compute that its Tutte polynomial is y2 (y3 +

y2 + y + x).

68 Chapter 8. IBIS groups

(b) If we are told that the group arises from a linear code C, then we can de-

duce that WC (X,Y ) = X 3 + 3XY 2 . In general the Tutte polynomial is not

computable from the weight enumerator, but in this case the code must be

the even-weight code and so the Tutte polynomial of the code matroid is

x2 + x + y. Now Proposition 7.1 shows that the Tutte polynomial of the

group matroid is y4 + 2y3 + 3y2 + y + 3xy + x2 + x.

This matroid on 6 elements in case (b) arises from two different base-transitive

groups of order 24, each isomorphic to the symmetric group S4 . These were both

considered in Chapter 6; one is the action of S4 on the set of 2-element subsets of

{1, . . . , 4}, and the other is the action of the rotation group of the cube on the set

of faces. Using any of several methods we™ve seen, it follows that, for any such

1

group G, we have PG (x) = 24 (x6 + 9x2 + 14). However, the stabiliser of a point is

the Klein group of order 4 in the ¬rst case and is the cyclic group in the other, so

the two groups have different cycle index. (See Exercise 6.4.)

8.7 The Tutte cycle index

As we have seen, for some IBIS groups the Tutte polynomial can be obtained

from the cycle index but not vice versa, while for others it is the opposite way

round. Is there a polynomial from which both the Tutte polynomial and the cycle

index can be obtained? In this section we construct such a polynomial.

Following the de¬nition of the Tutte polynomial, we try for a sum, over sub-

sets, of “local” terms. First, some terminology and observations. Let G be a

permutation group on „¦. For any subset ∆ of „¦, G∆ and G(∆) are the setwise and

pointwise stabilisers of ∆, and G[∆] the permutation group induced on ∆ by its

setwise stabiliser (so that G[∆] ∼ G∆ /G(∆) ). Let b(G) denote the minimum size

=

of a base for G. (This is the rank of the associated matroid if G is an IBIS group.)