<<

. 2
( 3)



>>

If we represent the permutation g as a function digraph, with edges (±, ±g) for all
± ∈ „¦, 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.)

<<

. 2
( 3)



>>