Combinatorics 2:

Structure, symmetry and

polynomials

1
Preface
This is the second of a three-part set of lecture notes on Advanced Combinatorics,
for the module MT5821 of that title at the University of St Andrews.
The syllabus for the module describes the three options as follows:

1. Enumerative combinatorics: basic counting, formal power se-

ries and their calculus, recurrence relations, q-analogues, group
action and cycle index, species, asymptotic results.
2. Graphs, codes and designs: strongly regular graphs, t-designs,
optimality for block designs, codes and weight enumerators,
matroids and Tutte polynomial, MacWilliams relations.
3. Projective and polar spaces: geometry of vector spaces, com-
binatorics of projective planes, sesquilinear and quadratic forms
and their classification, diagram geometry, classical groups.

These notes refer to the second section, delivered for the first time in the second
semester of 2014–2015, though in the event the focus was a bit different.

The first part dealt mostly with enumeration. The essential tool there is the
formal power series, an algebraic gadget which summarises a sequence of num-
bers, typically the answers to a sequence of counting problems, for example “How
many graphs with n vertices are there, for n = 1, 2, . . .?” This approach can handle
counting up to symmetry, using the notions of cycle index and species.
In Part 2, we move more towards structural combinatorics. The algebraic tools
tend to be polynomials rather than formal power series. We look at codes and their
weight enumerators, graphs and their chromatic polynomials, and (unifying these)
matroids and their Tutte polynomials. We also revisit questions of symmetry,
and cover the orbit-counting lemma and cycle index theorem. Some questions
which bring us over the boundary of what is currently known involve combining
structural and symmetry considerations.
A few less standard topics were also covered, including codes over Z4 (and
the Gray map), IBIS groups, and symmetric Sudoku.
The topics covered in the course can be inferred from the contents page.

Peter J. Cameron
April 2015

2
Contents
1 Error-correcting codes 5
1.1 Catching a liar . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
1.2 An example . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
1.3 Generator and parity check matrix, dual code . . . . . . . . . . . 10
1.4 Distance, weight, weight enumerator . . . . . . . . . . . . . . . . 12
1.5 MacWilliams’ Theorem . . . . . . . . . . . . . . . . . . . . . . . 14
1.6 The main issues in coding theory . . . . . . . . . . . . . . . . . . 17

2 Codes over Z4 22
2.1 The puzzle . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
2.2 The Gray map . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
2.3 Chains of binary codes . . . . . . . . . . . . . . . . . . . . . . . 25

3 Graph colouring 29
3.1 Graphs and colourings . . . . . . . . . . . . . . . . . . . . . . . 29
3.2 First proof: Inclusion–Exclusion . . . . . . . . . . . . . . . . . . 31
3.3 Second proof: Deletion–Contraction . . . . . . . . . . . . . . . . 32
3.4 Stanley’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . 35
3.5 Colours interchangeable . . . . . . . . . . . . . . . . . . . . . . 37

4 Graph colouring and symmetry 40

4.1 A problem from METRO . . . . . . . . . . . . . . . . . . . . . . 40
4.2 Counting up to symmetry . . . . . . . . . . . . . . . . . . . . . . 41
4.3 Orbital chromatic polynomial . . . . . . . . . . . . . . . . . . . . 43
4.4 What we can’t yet do . . . . . . . . . . . . . . . . . . . . . . . . 45
4.5 Example: the Petersen graph . . . . . . . . . . . . . . . . . . . . 45

5 Matroids 50
5.1 Definition and examples . . . . . . . . . . . . . . . . . . . . . . 50
5.2 Properties of matroids . . . . . . . . . . . . . . . . . . . . . . . . 52
5.3 Graphic matroids, planarity and duality . . . . . . . . . . . . . . 54

6 Tutte polynomial 60
6.1 Deletion and contraction . . . . . . . . . . . . . . . . . . . . . . 60
6.2 The Tutte polynomial . . . . . . . . . . . . . . . . . . . . . . . . 61
6.3 Tutte polynomial and chromatic polynomial . . . . . . . . . . . . 63

3
7 Matroids and codes 67
7.1 The correspondence . . . . . . . . . . . . . . . . . . . . . . . . . 67
7.2 Graphic matroids . . . . . . . . . . . . . . . . . . . . . . . . . . 69
7.3 Greene’s Theorem . . . . . . . . . . . . . . . . . . . . . . . . . . 70
7.4 Matroids and Steiner systems . . . . . . . . . . . . . . . . . . . . 73

8 Cycle index 75
8.1 The definition . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
8.2 The Cycle Index Theorem . . . . . . . . . . . . . . . . . . . . . 76
8.3 Sketch proof of the Cycle Index Theorem . . . . . . . . . . . . . 79
8.4 Permutation character . . . . . . . . . . . . . . . . . . . . . . . . 79
8.5 Factorisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81

9 IBIS groups 83
9.1 Bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83
9.2 IBIS groups . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 85
9.3 Examples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86
9.4 Codes and matroids revisited . . . . . . . . . . . . . . . . . . . . 87
9.5 Greedy bases . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90

10 Miscellanea 93
10.1 The Mathieu group M24 and its operands . . . . . . . . . . . . . . 93
10.2 Symmetric Sudoku . . . . . . . . . . . . . . . . . . . . . . . . . 96

4
1 Error-correcting codes
In this section of the notes, we have a quick look at coding theory. After a mo-
tivating introduction, we discuss the weight enumerator of a code, and the dual
code, and prove the MacWilliams identities relating the weight enumerators of a
code and its dual.

1.1 Catching a liar

Think of an integer in the range 0 to 15 (inclusive).
Now answer the following questions.
You are permitted to lie once.

• Is the number 8 or greater?

• Is it in the set {4, 5, 6, 7, 12, 13, 14, 15}?

• Is it in the set {2, 3, 6, 7, 10, 11, 14, 15}?

• Is it odd?

• Is it in the set {1, 2, 4, 7, 9, 10, 12, 15}?

• Is it in the set {1, 2, 5, 6, 8, 11, 12, 15}?

• Is it in the set {1, 3, 4, 6, 8, 10, 13, 15}?

If I don’t make a mistake, I can tell you both the number you thought of, and
the question you lied to (if any).

5
How it works
In what follows, be careful to distinguish between base 2 and modulo 2. The
first is simply a representation of integers using the digits 0 and 1. The second
is much more important to us: in place of integers, we re-interpret addition and
multiplication in the binary field GF(2) = {0, 1} of integers modulo 2, allowing
us to do linear algebra in the usual way.
First, let us see what happens if no lie is told. The chosen number is in the
interval [0, 15], and so it can be written in base 2 with four digits (padding on the
left with zeros if necessary). Suppose that the chosen number is 13. In base 2,
this is 1 · 8 + 1 · 4 + 0 · 2 + 1 · 1, that is, 1101. Moreover, the answers to the first
four questions are YES, YES, NO, YES. The purpose of these questions is simply
to convert the format, from an integer to a binary string. (The numbers for which
the answer to the ith question is YES are precisely the numbers with 1 in the ith
position in base 2.)
The next three questions add “check digits” to provide the error correction.
If the number in base 2 is x1 x2 x3 x4 , then it can be checked that the numbers for
which the answer to the fifth question are precisely those for which x2 +x3 +x4 = 1
(where the arithmetic is modulo 2). Similarly, for the sixth question, x1 +x3 +x4 =
1; and for the seventh, x1 + x2 + x4 = 0. In particular, for the number 13, or 1101,
the answers are NO, NO, YES, giving the 7-tuple 1101001.
We can write this in terms of linear algebra. Let G be the matrix
 
1 0 0 0 0 1 1
0 1 0 0 1 0 1
G= 0 0 1 0 1 1 0.


0 0 0 1 1 1 1

If v is the binary 4-tuple representing the number chosen, then vG is the 7-tuple
recording the correct answers to the questions.
Now it is not difficult to write down the sixteen 7-tuples which represent the
correct answers for each of the sixteen possible numbers. If you do this, you will
find two things:

• These sixteen vectors form a 4-dimensional subspace of the vector space

GF(2)7 of all 7-tuples. (This is clear, since they actually form the row space
of the matrix G.)

• Any two of the sixteen vectors differ in at least three coordinates. (Since
they form a subspace, we can see this more simply. The difference between

6
 two of the vectors is just another vector in the space, so we only have to
check that each of the sixteen vectors has at least three ones.)

Now suppose that the incorrect answer to one of the questions is given. Then
the 7-tuple of answers to the questions will not be an element of our chosen sub-
space, but will differ in one position from the tuple giving the correct answers.
Now an arbitrary vector cannot differ in one position from two different vectors
v1 and v2 of the subspace; for, if it did, these two vectors would differ in only two
positions, contrary to our observation.
This shows that in principle the correct answer can be determined: run through
the sixteen vectors until one is found which either coincides with the answers
given, or differs in one position. This vector will give the correct answers, and the
position of difference (if any) will give the number of the incorrect position. Then
the number thought of is found by taking the first four digits of the correct answer,
and interpreting them as the base-2 digits of an integer.
To simplify the process, we use a procedure known as syndrome decoding. We
are thinking of the responses to the questions as having the form “message plus
error”, where the message lies in the 4-dimensional subspace and the error is a
vector with at most one entry 1. Rather than find the message directly, we instead
first find the error. To do this, we require a map S on the set of 7-tuples with the
properties

• S is linear (so that we obtain S(message) + S(error));

• the sixteen allowable messages lie in the kernel of S (so that S(message) =
0);

• S, restricted to the possible errors, is one-to-one (so that S(error) determines

error).

Such a map is called a syndrome. Once the error is determined, we find the correct
message by simply undoing the error.
The syndrome is linear, so should be given by a matrix. To ensure the second
condition above, it is natural to take the rows of the matrix to span the null space
of the matrix G. In other words, we want a matrix H whose row space is the null
space of G. A small calculation shows that
 
0 0 0 1 1 1 1
H = 0 1 1 0 0 1 1.
1 0 1 0 1 0 1

7
This matrix has the remarkable property that its columns are the base 2 repre-
sentations of the integers from 1 to 7. In other words, if we calculate the dot
product of the rows of H with the answers given to the question, the three binary
digits we find are either all 0 (in which case no error occurred) or are the base-2
representation of the number of the row in which the error occurred.
If you actually want to try this out on your friends, there is one further piece
of information which simplifies the mental arithmetic required. It is based on the
following diagram of a structure known as the Fano plane.
1 u
T
'$
u u
 T
3
b u" "T 5
 b"b7 T
"" bbT
 &%
u
" u bTu
2 6 4
If you can draw the figure, you then put the first three powers of 2 (namely 1,
2, 4) on the vertices of the triangle, and then the third point on each line is labelled
with the sum of the other two labels.
From this picture, the correct answers to the questions can be read off. Apart
from 0000000 (for the number 0) and 1111111 (for the number 15), any number
either has 1s in the positions indicated by labels on a line and 0s in the other
positions, or similar with 0s and 1s swapped. For example, we saw that for 13,
the correct answers are 1101001, where the zeros are in the positions 3, 5, 6 (the
labels on the circular “line”). With this information, proceed as follows:

• If the answers contain no 1s, then no lie was told.

• If the answers contain a single 1, then its position is that of the lie.

• If the answers contain two ones, these two positions are contained in pre-
cisely one set of three labels corresponding to a line in the diagram; the third
label in the set is the position of the lie.

• If the answers contain three ones, there are two possibilities. Either these
three are the labels of a line, in which case no lie was told; or the positions of
the four zeros contain a unique label set, and the fourth zero is the position
of the lie.

• If the answers contain more than three ones, switch zeros and ones in the
above analysis.

8
1.2 An example
The previous suggestion describes a party trick, but at the basis of it is a code
known as the binary Hamming code of length 7. Here is an example of how this
code might be used in a practical set-up involving information transmission.
Suppose that we are transmitting information, in the form of a long string of
binary digits, over a channel. There is a small probability, say 1 in 106 , that a bit
error occurs, that is, the received bit is not the same as the transmitted bit; errors in
different bits are independent. In the course of sending, say, 1000 bits, the chance
3
of an error is 1 − (1 − 10−6 )10 , or about 1 in 1000, which may be unacceptably
high.
Suppose that instead we adopt the following scheme. Break the data into
blocks of four. Now for each 4-tuple a = (a1 , a2 , a3 , a4 ), we encode it by multi-
plying by the matrix
 
1 0 0 0 0 1 1
0 1 0 0 1 0 1
G= 0 0 1 0 1 1 0.


0 0 0 1 1 1 1

(Arithmetic is performed in the binary field GF(2).) The first four bits of c = aG
are just the bits of a; the purpose of the other three bits is error correction. We
transmit the string c.
Suppose that a 7-tuple b is received. We calculate s = bH, where
 
0 0 1
0 1 0
 
0 1 1
 
H = 1 0 0.

1 0 1
 
1 1 0
1 1 1

So s is a vector of length 3 whose components are the dot products of b with the
thre rows of H > .
If s = 0, we assume that b is the transmitted codeword. Otherwise, s is the
base 2 representation of an integer i in the range 1, . . . , 7; we assume that there
was a single bit error in position i, that is, we complement the ith entry of b. Then
we read the first four bits of b and assume that these were the bits transmitted.

9
 We will see shortly that our assumptions are correct provided that at most one
error occurs to the bits of b. So the probability that the assumptions are wrong
is 1 − (1 − 10−6 )7 − 7 × 10−6 (1 − 10−6 )6 , which is about 2.1 × 10−11 . Now we
have to send 250 blocks, so the error probability is about 1 in 190 000 000, much
smaller than before!
It remains to justify our claims. First, by listing all the 7-tuples of the form aG,
we find that each of them except 0 has at least three 1s. Moreover, since this set C
is just the row space of G, it is closed under subtraction; so any two elements of
C differ in at least three [Link] means that, if at most one error occurs, the
resulting vector b is either in C (if no error occurs) or can be uniquely expressed
in the form c + ei , where c ∈ C and ei is the vector with 1 in position i and zero
elsewhere. In the latter case, c was the sequence transmitted.
Now we can also check that cH = 0 for all c ∈ C. (For this, it is enough to
show that GH = 0, since vectors in C have the form aG.) Then

(c + ei )H = ei H = ith row of H,

and H has the property that its ith row is the base 2 representation of i. So our
claims about the correctness of the decoding procedure (assuming at most one
error) are justified.
The price we pay for the much improved error correction capability of this
scheme is slower transmission rate: instead of 1000 bits, we have to send 1750
bits through the channel. We say that the rate of the code is 4/7.
To summarise: we encode the information (in blocks of four bits) as elements
of the set C, and transmit these. The properties of C permit error correction. We
call the set C a code, and its elements codewords.

1.3 Generator and parity check matrix, dual code

Let F be a set called the alphabet and n a positive integer. A word of length n over
F is simply an n-tuple of elements of F; sometimes we write a1 a2 · · · an instead of
(a1 , a2 , . . . , an ). In the most important case here, F is a field; in this chapter, this
is always assumed to be the case. A code is just a set of words, that is, a subset
of F n . We always require a code to have at least two words, since a code with
one word would convey no information (since we would know for certain what
message was sent). The words in a code are called codewords.
The code C is linear over the field F if it is a subspace of F n . A linear code of
length n and dimension k is referred to as an [n, k] code.

10
 From an algebraic point of view, a linear [n, k] code is a k-dimensional sub-
space of an n-dimensional vector space with a fixed basis. It is this basis which
makes coding theory richer than the elementary theory of a subspace of a vector
space.
Let C be a [n, k] code. We can describe C by a generator matrix G, a k × n
matrix G whose rows form a basis for C, so that

C = {aG : a ∈ F k }.

We can also describe C by a parity check matrix H, a (n − k) × n matrix such that

C is the null space of H > , that is,

C = {c ∈ F n : cH > = 0}.

(This is the transpose of the matrix H of the preceding section.)

The generator and parity check matrices for a given code are of course not
unique. Indeed, elementary row operations applied to a matrix do not change
either its row space or its null space. So we can apply these operations to any
generator matrix (or parity check matrix) for a code and find another one.
From elementary linear algebra we know that elementary row operations can
be used to convert any matrix (with rank equal to number of rows) into one in
reduced echelon form, satisfying the following conditions:

• the first non-zero entry in any row is a 1 (a so-called “leading 1”);

• leading ones in lower rows occur further to the right;
• all the other entries in the column containing a leading 1 are 0.

So any linear code has a generator matrix in reduced echelon form.

If we are allowed to apply permutations to the positions in the codeword, we
can move all the columns with leading 1s to the front. Such a permutation doesn’t
change important properties of the code, such as its minimum weight. So, up to
such permutations, every linear code has a generator matrix of the form G = [Ik , P],
where P is k × n − k. Note that, with such a matrix, we have

xG = (x, xP),

so the first k symbols of a codeword represent the information transmitted (as in

our examples), while the other n − k are for error correction.

11
 The dual code C⊥ of C is the set

C⊥ = {x ∈ F n : x · c = 0 for all c ∈ C},

where · denotes the standard inner product on F n : that is,

a · b = a1 b1 + a2 b2 + · · · + an bn .

Proposition 1.1 A generator matrix for C is a parity check matrix for C⊥ , and
vice versa. 

If C is an [n, k] code, then its generator and parity check matrices are k × n
and (n − k) × n matrices G and H (with linearly independent rows) satisfying
GH > = 0. The fact that G is a parity check matrix for C⊥ holds because the
words of C⊥ are those satisfying xH > = 0. Then GH > = 0 implies HG> = 0, so
the statement that H is the generator matrix for C⊥ follows.
In particular, if G = [Ik , P], then H = [−P> , In−k ]; for these matrices have
linearly independent rows, and

GH > = [Ik , P][−P> , In−k ]> = −P + P = 0.

As an example, the dual of the [7, 4] code C in our introductory example (the
Hamming code) is the [7, 3] code consisting of the zero vector and the words of
weight 4 in C. (Exercise: Check this!)

1.4 Distance, weight, weight enumerator

The Hamming distance d(a, b) between words a and b is the number of coordi-
nates where they differ:

d(a, b) = |{i : 1 ≤ i ≤ n, ai 6= bi }|.

Let e be a positive integer. The code C is e-error-correcting if, for any word
v, there is at most one codeword c ∈ C for which d(v, c) ≤ e. Thus, if C is used
for transmitting information, and up to e errors occur during the transmission of a
codeword, then the correct codeword can be recovered uniquely.
The minimum distance of C is the smallest distance between two different
codewords. By the Triangle Inequality, if the minimum distance is at least 2e + 1,
then C is e-error-correcting: for, if d(v, c1 ) ≤ e and d(v, c2 ) ≤ e, then d(c1 , c2 ) ≤
2e. Conversely, if the minimum distance is 2e or smaller, it is easy to find a word
lying at distance e or smaller from two different codewords. So we have:

12
Proposition 1.2 A code is e-error-correcting if and only if its minimum distance
is at least 2e + 1. 

The weight wt(c) is the number of non-zero coordinates of c, that is, wt(c) =
d(c, 0), where 0 is the all-zero word. The minimum weight of C is the smallest
weight of a non-zero codeword.

Proposition 1.3 If C is linear, then its minimum distance is equal to its minimum
weight.

Proof Since wt(c) = d(c, 0), every weight is a distance. Conversely, d(c1 , c2 ) =
wt(c1 − c2 ); and, since C is linear, c1 − c2 ∈ C; so every distance is a weight. 

Thus, the minimum weight is one of the most significant parameters of a linear
code. Indeed, if an [n, k] code has minimum weight d, we sometimes describe it
as an [n, k, d] code.
If F is finite, the weight enumerator WC (X,Y ) of the code C is the homoge-
neous polynomial
n
WC (X,Y ) = ∑ X n−wt(c)Y wt(c) = ∑ AiX n−iY i,
c∈C i=0

where Ai is the number of words of weight i in C.

A simple example of a code is the binary repetition code of length n, consisting
of the two words (0, 0, . . . , 0) and (1, 1, . . . , 1); its minimum weight is clearly n.
Its dual is the binary even-weight code consisting of all words of even weight; its
minimum weight is 2.
The Hamming code of the previous section is a [7, 4] binary linear code. If
a = 1100, then aG = 1100110, a word of weight 4. Repeating for all 4-tuples a,
we find that the code contains seven words of weight 3 and seven of weight 4, as
well as the all-0 and all-1 words (with weight 0 and 7 respectively). So the weight
enumerator is
X 7 + 7X 4Y 3 + 7X 3Y 4 +Y 7 ,
the minimum weight is 3, the minimum distance is also 3, and the code is 1-error-
correcting (which should come as no surprise given the decoding procedure for
it).
Further calculation shows that the dual code C⊥ consists of the zero word and
the seven words of weight 4 in C; its weight enumerator is X 7 + 7X 3Y 4 , and its
minimum weight is 4.

13
 No brief account of codes would be complete without mention of the cele-
brated binary Golay code. This is a [24, 12, 8] code with weight enumerator

X 24 + 759X 16Y 8 + 2576X 12Y 12 + 759X 8Y 16 +Y 24 .

This code is self-dual, that is, it is equal to its dual. Its automorphism group is the
Mathieu group M24 .

1.5 MacWilliams’ Theorem

From the weight enumerator of a code C, we can calculate the weight enumerator
of the dual code C⊥ , using the theorem of MacWilliams:

Theorem 1.4 Let C be an [n, k] code over GF(q). Then the weight enumerators
WC and WC⊥ of C and its dual are related by

1
WC⊥ (X,Y ) = WC (X + (q − 1)Y, X −Y ).
|C|

Proof We give here the classical proof, which is algebraic in nature. Later, we
will see a different, combinatorial proof. Put A = GF(q).
A character of the additive group A+ of A is a function χ from A to the non-
zero complex numbers satisfying χ(a + b) = χ(a)χ(b) for all a, b ∈ A. There is
a trivial character χ1 given by χ1 (a) = 1 for all a ∈ A. For the proof we need a
non-trivial character.

• If A = GF(2) = {0, 1}, take χ(0) = 1, χ(1) = −1.

• if q is a prime p and A = GF(p) = Z/(p), then take

χ(a) = e2πik/p .

• In general it can be shown that non-trivial characters always exist, but we

will not stop to prove it here.

We need to show the following lemma: If χ is non-trivial then

∑ χ(a) = 0.
a∈A

14
To prove this, choose b with χ(b) 6= 1 (this exists by assumption), and let S =
∑a∈A χ(a). Then the elements a + b run through A as a does, and so we have
S= ∑ χ(a + b) = ∑ χ(a)χ(b) = Sχ(b).
a∈A a∈A

So S(1 − χ(b)) = 0, and hence S = 0.

So to the proof. Let f (v) = X n−wt(v)Y wt(v) for v ∈ GF(q)n (a term in the sum
for the weight enumerator), and
g(u) = ∑ χ(u · v) f (v)
v∈GF(q)n

for u ∈ GF(q)n . Then we have

∑ g(u) = ∑ f (v) ∑ χ(u · v).

u∈C v∈GF(q)n u∈C

We evaluate this sum in two ways. First, note that the inner sum on the right
is equal to |C| if v ∈ C⊥ , since χ(0) = 1; and, for v ∈
/ C⊥ , χ(u · v) takes each value
in GF(q) equally often, so the sum is zero. So the whole expression is |C| times
the sum of the terms f (v) over v ∈ C⊥ , that is,

∑ g(u) = |C|WC⊥ (X,Y ).

u∈C

On the other hand, if we put


0 if x = 0,
δ (x) =
1 if x 6= 0,
for x ∈ GF(q), then, with u = (u1 , . . . , un ), we have
n
g(u) = ∑ ∏ X 1−δ (vi)Y δ (vi) χ(u1v1 + · · · + unvn)
v1 ,...,vn ∈GF(q) i=1
n
1−δ (v) δ (v)
= ∏ ∑ X Y χ(ui v).
i=1 v∈GF(q)

(See below for this.)

Now the inner sum here is equal to X + (q − 1)Y if ui = 0, and to X − Y if
ui 6= 0. So
g(u) = (X + (q − 1)Y )n−wt(u) (X −Y )wt(u) ,
and ∑u∈C g(u) = WC ((X + (q − 1)Y, X −Y ). So we are done. 

15
 The point noted in this proof is a general form of “expanding brackets”. Sup-
pose that we have an expression of the form
n
∏ ∑ fi(v).
i=1 v∈A

This is a product of terms each of which is a sum over A. Expanding the brackets,
we will get a sum of |A|n terms, each obtained by choosing one element from each
of the n brackets and multiplying them: if vi is chosen from the ith bracket, we get
n
∑ f1 (v1 ) · · · fn (v)n) = ∑ ∏ fi(vi).
v1 ,...,vn ∈A v1 ,...,vn ∈A i=1

We saw that the weight enumerator of the Hamming code is X 7 + 7X 4Y 3 +

7X 3Y 4 +Y 7 . So the weight enumerator of the dual code is
1
((X +Y )7 +7(X +Y )4 (X −Y )3 +7(X +Y )3 (X −Y )4 +(X −Y )7 = X 7 +7X 3Y 4 ,
16
as we showed earlier.

Example What can we say about the weight enumerator of a linear binary code
C with the following properties:
• C = C⊥ , that is, C is self-dual;

• C contains words of weights 0, 8, 12, 16, 24 only.

The first assumption implies that every word in C is orthogonal to itself, and
so has even weight. But then every word in C is orthogonal to the all-1 word 1,
so 1 ∈ C⊥ . Now, since C = C⊥ , we see that C does contain the unique word of
weight 24. Also, adding 1 to anything interchanges 0s and 1s. So C has equally
many words of weight 8 and 16. Also, dim(C) = 12, so |C| = 212 = 4096.
Thus we have

WC (X,Y ) = X 24 + aX 16Y 8 + (4094 − 2a)X 12Y 12 + aX 8Y 16 +Y 24 .

Since C = C⊥ , MacWilliams’ Theorem tells us that

1
WC (X +Y, X −Y ) = WC (X,Y ).
4096

16
 It is not hard to see that the coefficients of odd powers of Y are all zero in the
left-hand expression. Let us compute the coefficient of X 22Y 2 . We get
      
1 24 8 16
2 + 2a − 16 · 8 +
4096 2 2 2
   
12 12
+ (4094 − 2a) − 12 · 12 + = 0,
2 2
whence 64a − 48576 = 0, or a = 759.
So such a code must have 759 words of weight 8, 2576 of weight 12, and 759
of weight 16.
Indeed, there is a unique code with these properties, the extended binary Golay
code, a very interesting object connected with the Steiner system S(5, 8, 24), the
Mathieu group M12 , and the Leech lattice in 24 dimensions, and hence on to the
Monster simple group, moonshine, string theory, . . . [The exercises at the end of
this chapter include a construction of the extended Golay code.]

1.6 The main issues in coding theory

The obvious requirements for a good error-correcting code are
(a) Good error-correction: codewords should be far apart (in terms of Hamming
distance), so there is little chance of mistaking one for another.
(b) Many codewords, so that information can be transmitted at a high rate.
We can summarise both of these requirements in numbers: the minimum dis-
tance of the code, the smallest distance between two codewords (so that, as we
have seen, a code with minimum distance 2e + 1 or greater will correct up to e
errors during transmission), and the rate, which is defined as follows.
Suppose that the alphabet A contains q symbols, and that we have a code C
with length n over A. We can transmit information using C, by encoding k-tuples
of symbols from A as codewords. There must be at least enough words in C to
allow such an encoding; that is, |C| ≥ qk , or k ≤ logq |C|. Information which would
take k time-steps to send without encoding will take n time-steps if we use C. So
we define the rate of the code C to be logq |C|/n.
Note that, if A is a finite field and C is a linear code of dimension k over A,
then |C| = qk ; so the rate of C is k/n.
Now it is clear that there is a tension between these two parameters: if we
arbitrarily increase the rate, we eventually end up with codewords only one step

17
apart, and the code will not correct any errors. There are various results (including
the sphere-packing bound, given on Problem Sheet 1) which give an upper bound
for C (and hence for the rate) in terms of the number of errors corrected.
But there is another issue, which is not so often discussed.
3. The code should be easy to implement: we should be able to implement
the encoding and decoding functions within the limitations of our existing
hardware.
This is not so easily quantified. It has focussed the attention of coding theorists
on special codes for which good algorithms are known. Here are a couple of
comments.
• One of the earliest uses of coding theory was in interplanetary space probes.
The probes were quite small and low-powered; for example, a typical early
probe had a 400 watt power supply, of which 30 watts was used for the
transmitter. Encoding of linear binary codes is ideal here, since it is a linear
operation x 7→ xG (where G is the generator matrix) which can be carried
out very efficiently with a small purpose-built circuit. In this case, we can
allow decoding to be more difficult, since we can build large radio antennae
and computers on earth for this job.
• Nevertheless, there are limitations. A code with block length n requires n
symbols to be stored before decoding can begin; if n is too large, we may
not have the memory to do this, or be prepared to wait for the answer.
• Computational complexity theorists have shown that the problem of decod-
ing an arbitrary linear code is NP-hard (this implies that no known algorithm
solves the problem in a number of steps polynomial in the size of the input
data), although encoding such a code is in P.

Shannon’s Theorem
The founder of information theory, Claude Shannon, proved a remarkable the-
orem about the issues above, which I will describe briefly and without proof. With
any communication channel, Shannon defines a number between 0 and 1 called
the capacity of the channel. (If the channel introduces errors to single symbols
with probability p and the errors are independent, the capacity is a function of p,
given by 1 − p log p − q log q, where q = 1 − p and the base of the logarithms is
the alphabet size; but Shannon’s theorem deals with much more general types of
channel.) His theorem asserts:

18
 Given a communication channel with capacity c, and positive num-
bers δ and ε, there is a code C with rate at least c − δ so that the
probability of error during the transmission of a single codeword is
less than ε.
In other words, we can transmit information at rates up to the channel capacity
without any compromise on error correction!
A couple of comments are relevant.
• Shannon’s construction produces very long codes, so his theoretical bound
is not at all practical. We still need the work of coding theorists on practical
codes.
• The most remarkable thing is the construction: Shannon chooses the appro-
priate number of codewords by picking at random from the set of all words.
He shows that the probability of picking two words close together is small,
and the probability of failing to correct a random error is also small.

Exercises
1.1. Let H be the d × 2d − 1 matrix whose columns are the base 2 representa-
tions of the integers 1, . . . , 2d − 1. Show that the [2d − 1, 2d − d − 1] binary code
with parity check matrix H is 1-error-correcting, and devise a syndrome decoding
method for it.
1.2. You are given 12 coins, one of which is known to be either lighter or heavier
than all the others; you are also given a beam balance. Devise a scheme of three
weighings which will identify the odd coin and determine if it is light or heavy; the
coins weighed at each step should not depend on the results of previous weighings.
What is the connection between this problem and error-correcting codes over Z3 =
{0, +1, −1}?
1.3. The direct sum C1 ⊕C2 of two codes C1 and C2 is obtained by concatenating
each word of C1 with each word of C2 . Show that if Ci is a [ni , ki , di ] code for
i = 1, 2, then C1 ⊕ C2 is a [n1 + n2 , k1 + k2 , min{d1 , d2 }] code. Show also that
WC1 ⊕C2 (X,Y ) = WC1 (X,Y )WC2 (X,Y ). Show also how to construct
(a) a [n1 + n2 , min{k1 , k2 }, d1 + d2 ] code;
(b) a [n1 n2 , k2 k2 , d1 d2 ] code.
Why is there no general construction of a [n1 + n2 , k1 + k2 , d1 + d2 ] code?

19
1.4. A code (not necessarily linear) is said to be systematic in a given set of k
coordinate positions if every k-tuple of symbols from the alphabet occurs in these
positions in exactly one codeword. (Such a code contains qk codewords, where k
is the size of the alphabet.)

(a) Prove that a linear code is systematic in some set of coordinate positions.

(b) Prove that a code of length n which is systematic in every set of k coordinate
positions has minimum distance d = n − k + 1.

(A code with the property of (b) is called a maximum distance separable code, or
MDS code.)
1.5. Let A be the binary code spanned by the word 01101001 and all words
obtained by cyclic shifts of the first seven positions (fixing the last position). Show
that A is a [8, 4, 4] code. (This is an extended Hamming code.)
Let X be obtained from A by reversing the first seven positions (fixing the last
position). Show that A ∩ X contains only the all-0 and all-1 words. Hence show
that
G = {(a + x, b + x, a + b + x) : a, b ∈ A, x ∈ X}
is a [24, 12, 8] code. (This is the (extended) Golay code.)
1.6. An octad in the Golay code is a set of eight coordinate positions supporting
a codeword of weight 8. For any codeword c ∈ G, let π(c) be the restriction of
c to the positions of an octad. Prove that {π(c) : c ∈ G} is the even-weight code
E8 of length 8. Now, for any subset X of E8 , let π ← (X) be the restriction to the
complement of the octad of the set {c ∈ C : π(c) ∈ X}. Show that

(a) π ← ({0}) is a [16, 5, 8] code;

(b) π ← (E8 ) is a [16, 11, 4] code (each word occurring from two different code-
words differing at all positions of the octad);

(c) If X = {00000000, 11000000, 10100000, 01100000}, then π ← (X) is a [16, 7, 6]

code;

(d) If X = {00000000, 11000000, 10100000, 10010000, 10001000, 10000100,

10000010, 10000001}, then π ← (X) is a nonlinear code consisting of 256
words of length 16 with minimum distance 6.

20
1.7. Prove that the Golay code, and the each of the codes constructed in (a),
(b) and (d) of the preceding exercise, is of maximum possible cardinality for a
binary code of its length and minimum distance. (Hint: Look up the Hamming
and Plotkin bounds. Part (d) is more difficult!)
1.8. Here are two [16, 8] codes:

(a) C1 = H ⊕ H, where H is the [8, 4] code defined above;

(b) C2 consists of all words of the form (v, v) and (v, v + 1), where v is a word
of length 8 with even weight, and 1 is the all-1 word of length 8.

Show that C1 and C2 are self-dual [16, 8] codes with the same weight enumerator.

21
2 Codes over Z4
2.1 The puzzle
What is the largest binary code of length 16 having minimum distance 6?
It turns out that no such code can have more than 256 codewords. This sug-
gests that there might be a linear code of dimension 8; but in fact it can be shown
that no such code exists, the largest dimension of a linear code with these param-
eters being 7.
The problem of constructing a code (necessarily non-linear) was posed by
Robinson, and solved by Nordstrom (who was a high-school student who hap-
pened to be in the audience of Robinson’s lecture). This code is now known as
the Nordstrom–Robinson code. It, and the 7-dimensional linear code, were con-
structed in Exercise 1.6.
The Nordstrom–Robinson code has several remarkable properties.
A code C of length n is said to be distance-invariant if, for any i ∈ {0, 1, . . . , n}
and any c ∈ C, the number Ai (c) of codewords at distance i from c depends only
on i, not on c. Any linear code is distance-invariant; for subtracting c from every
codeword doesn’t change distances, so Ai (c) = Ai (0) is the number of words of
weight i. It turns out that the Nordstrom–Robinson code, though non-linear, is
distance-invariant.
In a distance-invariant code, we can talk about the distance enumerator
n
F(X,Y ) = ∑ Ai (c)X n−iY i ,
i=0

since this does not depend on the choice of c. If the code is linear, it is just the
weight enumerator of the code. For the Nordstrom–Robinson code, the distance
enumerator is
F(X,Y ) = X 16 + 112X 10Y 6 + 30X 8Y 8 + 112X 6Y 10 +Y 16 .
Now some calculation shows that
1
F(X,Y ) = F(X +Y, X −Y ).
256
If the code were linear and self-dual, this would be the MacWilliams theorem. But
the code is not linear, so self-duality does not make sense!
In the early 1970s, the puzzle deepened. Two families of non-linear codes
were found by Kerdock and Preparata respectively: these are the Kerdock codes

22
Kn and the Preparata codes Pn . Each of Kn and Pn has length 4n+1 , and K1 = P1
is the Nordstrom–Robinson code.
• Each is better than any linear code with the same length and minimum dis-
tance.
• Each is distance-invariant, and their distance enumerators satisfy
1
FPn (X,Y ) = FK (X +Y, X −Y )
|Kn | n
(which implies the same equation with P and K reversed).
In other words, although they are non-linear, they behave like a dual pair of linear
codes!
The mystery remained for two decades, during which time some eminent
mathematicians speculated that it was just coincidence. Finally, it was resolved by
five authors, Hammons, Kumar, Calderbank, Sloane and Solé, in 1995. As well as
resolving the mystery, these authors did more. For a linear code, encoding is very
simple; decoding is not so simple, but we have general methods such as syndrome
decoding to help. For non-linear codes, on the face of it, encoding and (especially)
decoding are very hard. The authors showed how linear methods could be used
to implement all these non-linear codes. This is important because, as noted, they
are better than comparable linear codes.

2.2 The Gray map

The solution involves codes over the alphabet Z4 , the integers mod 4. We regard
the four elements of Z4 as being arranged around a circle, and define the dis-
tance dL between two of them as the number of steps apart they are: for example,
dL (1, 3) = 2, but dL (0, 3) = 1. Now we replace the Hamming distance between
two words a = (a1 , . . . , an ) and b = (b1 , . . . , bn ) of Zn4 by the Lee distance, defined
by
n
dL (a, b) = ∑ dL (ai , bi ).
i=1
Similarly the Lee weight of a is wtL (a) = dL (a, 0).
Now, if C is a Z4 -linear code, that is, an additive subgroup of Zn4 , then the Lee
weight enumerator of C is given by
LWC (X,Y ) = ∑ X 2n−wtL (c)Y wtL (c).
c∈C

23
(Note that the maximum possible Lee weight of a word of length n is 2n.)
It turns out that there is a version of MacWilliams’ Theorem connecting the
Lee weight enumerators of a Z4 -linear code C and its dual C⊥ (with respect to the
natural inner product).
The set Z4 , with the Lee metric dL , is isometric to the set Z22 with the Hamming
metric, under the Gray map γ, defined by
γ(0) = 00, γ(1) = 01, γ(2) = 11 γ(3) = 10.
2u 11
u
......................................
.......... .......
....... .....
..... ....
.. ... ...
@
.. . ...
... ... @
3 u u1 10 u @u01
... ..
..
... .
.. ..
...
...
.
... .
. @
... .
.... ..
..... ....
.....
.......
@
.......
..........
u
........................................ @u
0 00
The crucial property to observe is that the Lee distance between points on
the left (the number of steps round the circle) is equal to the Hamming distance
between the corresponding pairs on the right.

Digression A Gray code is an arrangement of the 2n binary n-tuples in a se-

quence so that any two terms in the sequence have Hamming distance 1. So, for
example, (00, 01, 11, 10) is a Gray code. Gray codes exist for all possible lengths
n. If (v1 , . . . , v2n ) is a Gray code for n-tuples, then we obtain a Gray code for
(n + 1) tuples as (v1 0, v2 0, . . . , v2n 0, v2n 1, . . . , v2 1, v1 1). Indeed, we see that this
construction gives us a circular sequence, since the Hamming distance between
the first and last terms is also 1.
Gray codes are used in analog-to-digital conversion. If you write the integers
from 0 to 2n − 1 in base 2, at various points in the sequence the distance between
consecutive terms can be large. If we take a reading when the quantity being
measured lies between two such values, then any of the changing digits could be
read incorrectly. (Imagine taking a reading from the odometer or mileage gauge
of a car as it was changing from 39999 to 40000: you might get any one of 32
values between 30000 and 49999.) If instead we use a Gray code, the possible
error is restricted to one digit, and we will get one of the values on either side of
the true reading.
Now we extend the definition of the Gray map to map from Zn4 to Z2n
2 by

γ(a1 , . . . , an ) = (γ(a1 ), . . . , γ(an )).

24
It is easily seen that γ is an isometry from Zn4 (with the Lee metric) to Z2n
2 (with
the Hamming metric).
The Gray map is non-linear, so the image of a Z4 -linear code C is usually a
non-linear binary code. But the isometry property shows that γ(C) is necessarily
distance-invariant (since the linear code C is), and that its distance enumerator is
equal to the Lee weight enumerator of C. Thus, taking a Z4 -linear code and its
dual, and applying the Gray map, we obtain a pair of formally self-dual non-linear
binary codes.
Hammons et al. show that, if this procedure is applied to the Z4 analogue of
the extended Hamming codes and their duals, then the Preparata and Kerdock
codes are obtained. Thus, the mystery is explained. (There is a small historical
inaccuracy in this statement. They obtained, not the original Preparata codes, but
another family of codes with the same weight enumerators, hence just as good in
practice.)
Here is an example of a linear Z4 code whose Gray map image is non-linear.
The code C is spanned by 011 and 112. So the 16 words are

000, 011, 022, 033, 112, 123, 130, 101,

220, 231, 202, 213, 332, 303, 312, 321,

and their Gray map images are

000000, 000101, 001111, 001010, 010111, 011110, 011000, 010001,

111100, 111001, 110011, 110110, 101011, 100010, 100111, 101101.

So the Gray map image of the code contains 000101 and 010111, but not their
sum 010010.
But the Lee weight enumerator of the Z4 -code and the Hamming weight enu-
merator of its Gray map image are both X 6 +6X 4Y 2 +9X 2Y 4 , equal as they should
be.
There is a temporary web page describing the Nordstrom–Robinson code at

[Link]

2.3 Chains of binary codes

Another approach to Z4 -linear codes is via a representation as pairs of Z2 -linear
codes. Let C be a Z4 -linear code. We construct binary codes C1 and C2 as follows.

25
C1 is obtained just by reading the words of C modulo 2; and C2 is obtained by se-
lecting the words of C in which all coordinates are even, and replacing the entries
0 and 2 mod 4 by 0 and 1 mod 2.
To state the next theorem, we must define a more general weight enumerator
associated with a Z4 -linear code C. This is the symmetrised weight enumerator of
C, defined as follows:

SWC (X,Y, Z) = ∑ X n0(c)Y n2(c)Z n13(c),

c∈C

where n0 (c) is the number of coordinates of C equal to zero; n2 (c) the number
of coordinates equal to 1; and n13 (c) the number of coordinates equal to 1 or 3.
Since these coordinates contribute respectively 0, 2, and 1 to the Lee weight, we
have
LWC (X,Y ) = SWC (X 2 ,Y 2 , XY ).
‘

Theorem 2.1 The pair (C1 ,C2 ) of binary codes associated with a Z4 -linear codes
C satisfies

(a) C1 ⊆ C2 ;

(b) |C| = |C1 | · |C2 |;

(c) WC1 (X,Y ) = SWC (X, X,Y )/|C2 | and WC2 (X,Y ) = SWC (X,Y, 0).

Proof (a) If v ∈ C, then doubling v gives a word with all coordinates even; the
corresponding word in C2 is obtained by reading v mod 2. So C1 ⊆ C2 .
(b) C1 is the image of C under the natural homomorphism from Zn4 to Zn2 which
simply reads each coordinate mod 2, and C2 is naturally bijective with the kernel
of this map; so |C| = |C1 | · |C2 |.
The proof of (c) is an exercise. 

We call a pair (C1 ,C2 ) of binary linear codes with C1 ⊆ C2 a chain of binary
codes.
Every chain of binary codes arises from a Z4 -linear code in the manner of the
theorem. For suppose that binary codes C1 and C2 are given with C1 ⊆ C2 . Let

C = {v1 + 2v2 : v1 ∈ C1 , v2 ∈ C2 },

26
where the elements 0 and 1 of Z2 are identified with 0 and 1 in Z4 for this construc-
tion. Then the preceding construction applied to C recovers C1 and C2 . So every
chain of codes (that is, every pair (C1 ,C2 ) with C1 ⊆ C2 ) arises from a Z4 -linear
code.
However, the correspondence fails to be bijective, and many important prop-
erties are lost. Fore example, the two Z4 -codes

{000, 110, 220, 330} and {000, 112, 220, 332}

give rise to the same pair of binary codes (with C1 = C2 = {000, 110}) but have
different symmetrised weight enumerators (and so different Lee weight enumera-
tors).
The problem of describing all Z4 -linear codes arising from a given chain has
not been solved. It resembles in some ways the “extension problem” in group
theory.

Exercises
2.1. Show that the Gray map image of the Z4 code spanned by 1111 and 0123 is
a (linear) self-dual [8, 4, 4] code.
2.2. Prove that the Nordstrom–Robinson code as defined in Exercise 1.6 is
distance-invariant and has the claimed weight enumerator.
2.3. Prove Theorem 2.1(c). Verify the conclusion directly for the two codes in the
example following the theorem. Construct the images of these two codes under
the Gray map.
2.4. Show that the Z4 -linear code with generator matrix
 
1 3 1 2 1 0 0 0
1 0 3 1 2 1 0 0
 
1 0 0 3 1 2 1 0
1 0 0 0 3 1 2 1

is equal to its dual and has Lee weight enumerator

X 16 + 112X 10Y 6 + 30X 8Y 8 + 112X 6Y 10 +Y 16 .

(This is the code whose Gray map image is the Nordstrom–Robinson code.)

27
2.5. Prove that, for any a, b ∈ Z4 , we have

γ(a + b) = γ(a) + γ(b) + (γ(a) + γ(−a)) ∗ (γ(b) + γ(−b)),

where ∗ denotes componentwise product: (a, b) ∗ (c, d) = (ac, bd).

Hence prove that a (not necessarily linear) binary code C is equivalent to the
Gray map image of a linear Z4 code if and only if there is a fixed-point-free
involutory permutation σ of the coordinates such that, for all u, v ∈ C, we have

u + v + (u + uσ ) ∗ (v + vσ ) ∈ C,

where ∗ is the componentwise product of binary vectors of arbitrary length.

(Define σ so that, if u = γ(c), then uσ = γ(−c); this permutation interchanges
the two coordinates corresponding to each coordinate of the Z4 code.)
2.6. Construct Gray codes of length n over the alphabet {0, 1, . . . , b − 1} for any
base b. Can you do a little bit more: Arrange the n-tuples in a sequence so that
any consecutive tuples in the sequence differ in only one position, and have x and
x + 1 there, in either order, for some x.
If you are familiar with the Tower of Hanoi puzzle, can you explain its con-
nection with a Gray code?

28
3 Graph colouring
3.1 Graphs and colourings
A graph is a structure which can be defined in several ways. We will take it to
be a pair (V, E), where V is a set of vertices, and E a set of edges: each edge is
incident with two vertices, which may or may not be equal. Thus, we allow our
graphs to have “loops” (edges which join a vertex to itself) and “multiple edges”
(different edges incident with the same pair of vertices). A graph is called simple
if it has neither loops nor multiple edges.
I assume that you are familiar with the notion of a connected graph (one in
which there is a path from any vertex to any other) and the connected components
of a graph.
In this section of the notes, you lose nothing by pretending that all graphs are
simple; but later, it will be necessary to have the general concept. The picture
shows, on the left, a general graph, and on the right, a simple graph.
u
.....
.........
h
u
........
.......
..
........
. @ @
. @ @
......
...
....
....
@ @
.. ...
.
... @ @
..
.....
.............. ..........u
........................... ....
...... @..u
..................
...................
....................... u @u
@
@ @
@
@ @
@ @
@.....u
... @h
u
. ..
... ..
.. ..
.... ....
...........

A proper vertex-colouring of a graph is a map from the vertex set of the graph
to a set C of colours with the property that the two vertices incident with any edge
must have different colours. Often we just say colouring, since this is the only
kind we will consider. The picture on the right shows a colouring of the graph
with a set of two colours, {red, blue}.
If a graph has a loop, then it has no proper colourings, since it is impossible for
the two ends of a loop to have different colours. If there are multiple edges, then
the notion of colouring is unchanged if we simply replace all the edges incident
with two vertices by a single edge. So in discussing graph colourings, we lose
nothing by assuming that our graphs are simple.
Every simple graph (indeed, any loopless graph) with finitely many vertices
has a colouring with a finite number of colours. (If we have at least as many

29
colours as vertices, we simply give each vertex a different colour.) Fewer colours
may suffice. The chromatic number χ(X) of a graph X is the smallest number of
colours with which X can be coloured.
Obviously a graph has chromatic number 1 if and only if it has no edges. (A
graph with no edges is called null.)
Suppose that X can be coloured with two colours. The sets of vertices of each
colour form a partition of the vertex set V into two parts V1 and V2 , and every edge
is incident with a vertex in V1 and a vertex in V2 . A graph which has such a vertex
partition is called bipartite. Conversely, a bipartite graph can be coloured with
two colours. Thus, a graph has chromatic number 2 if and only if it is bipartite but
not null.
It is easy to decide whether a graph is bipartite. It is enough to deal with each
connected component of the graph, so we can assume that X is connected. Take a
vertex v ∈ V and put it into a set V1 . Then put all neighbours of v into V2 , all their
neighbours into V1 , and so on. If a conflict arises, where the same vertex is put
into two different sets, the graph is not bipartite; but if the process terminates, we
have found a bipartition.
By contrast, deciding whether a graph has chromatic number r for given r ≥ 3
is a computationally “hard” problem: it is NP-complete, and so no polynomial-
time algorithm for it is known.
Here is a famous result which gives an upper bound on the chromatic number
of a graph. The maximum degree of a graph is the largest number of edges incident
with a single vertex.

Theorem 3.1 (Brooks’ Theorem) Let X be a connected simple graph with max-
imal degree r. Then X has chromatic number at most r, except in two situations
when the chromatic number is r + 1:

• X is a complete graph Kn , with n = r + 1;

• X is a cycle of odd length, with r = 2.

Proof I will not prove this result, but will just prove a simpler result to show
that the chromatic number is at most r + 1. Order the vertices of the graph, as
v1 , v2 , . . . , vn . Suppose that we have r + 1 colours available. Colour the vertices
sequentially. Since the maximum degree is r, when we come to colour any vertex
vi , at most r colours have been applied to its neighbour, and so there is a colour
free for vi .

30
 We are interested in counting colourings of a graph. We are going to give two
proofs of the following theorem: the function counting colourings of a graph is a
polynomial.

Theorem 3.2 Let X be a simple graph with n vertices. Then there is a unique
monic polynomial PX with integer components, having degree n, such that the
number of colourings of X with q vertices is PX (q) for any positive integer q.

The polynomial PX is called the chromatic polynomial of X.

The chromatic polynomial of a graph is unique. For if two different polyno-
mials P and Q both evaluated to the number of colourings with q colours for each
positive integer q, then the polynomial F(x) = P(x) − Q(x) would take the value 0
for any positive integer, contradicting the fact that a polynomial cannot have more
roots than its degree.
So what we have to do is to show that the counting function is given by a
polynomial.

3.2 First proof: Inclusion–Exclusion

This proof uses the Principle of Inclusion and Exclusion, or PIE for short, which
we now state.

Theorem 3.3 (Principle of Inclusion and Exclusion) Let A1 , . . . , An be subsets

of a finite set X. For I ⊆ {1, . . . , n}, let
\
AI = Ai ,
i∈I

with the convention that A0/ = X. Then

(−1)|I| |AI |.
[
X\ Ai = ∑
i∈{1,...,n} I⊆{1,...,n}

Proof The sum on the right-hand side can be regarded as being the sum, over all
elements x ∈ X, of a contribution from x which is the sum of appropriate signs for
the subsets AI which contain x.
If x lies in none of the sets Ai , then the only contribution from x corresponds
to the term I = 0/ in the sum, and so x contributes 1.

31
 Let K = {i ∈ {1, . . . , n} : x ∈ Ai }, and suppose that K 6= 0.
/ Let |K| = k. Then
the sets AI containing x are just those with I ⊆ K, and the contribution of x is
k  
|I| k
∑ (−1) = ∑ i (−1)i = (1 − 1)k = 0,
I⊆K i=0

by the Binomial Theorem.

So the sum counts precisely the points lying in no set Ai , as claimed.
Now we use this principle to construct the chromatic polynomial of a graph
X with vertex set V and edge set E. We let X be the set of all colourings of the
vertices of G, proper or improper; then |X| = qn , where n is the number of vertices.
For every edge e, let Ae be the set of colourings for which e is improperly coloured
(that is, its endpoints have the same colour).
Given a subset I of the edge set E, how many colourings have the property
that the edges in I (and maybe others) are improperly coloured? This means that
the vertices on any edge of I have the same colour; so, if we consider the graph GI
with vertex set V and edge set I, then all the connected components of GI have the
same colour. So there are qc(I) colourings, where c(I) is the number of connected
components of the graph (V, I).
By PIE, the number of proper colourings (those with no improper edges) is

∑ (−1)|I|qc(I).
I⊆E

This is clearly a polynomial in q. Moreover, the largest power of q is qn , occurring

just when I = 0;/ so it is a monic polynomial of degree n.
Why is this not a computationally efficient algorithm? Counting connected
components is easy; but we have to do this for exponentially many subsets of the
edge set.

3.3 Second proof: Deletion–Contraction

Let e be an edge of a graph X. We define two new graphs from X by deleting and
contracting the edge e, as follows:
• X\e (“X delete e”) is obtained simply by removing e from the edge set.
• G/e (“X contract e”) is obtained as follows: remove e, and identify the two
ends of e, each remaining incident with the other edges as in X. (Think of e
as carrying a very strong force which pulls the two vertices together.)

32
 u e u u u
u
T
 T
 T
X X\e  X/e T
 T
u u u u u
 Tu

What happens with multiple edges or loops? We have to address this since
contraction might create such things.

• Suppose that e is incident with v and w. If there are edges joining v to x and
w to x, for some external vertex x, then we will have a double edge in X/e.
While we are only interested in colourings, we can simply remove one of
the two edges; but later we will have to keep them.
• If X has several edges incident with v and w, then contracting one of them
will create a loop.
• We can delete loops, but it doesn’t make much sense to contract them!

The relevance of this to counting is:

Theorem 3.4 Let X be a simple graph with chromatic polynomial PX . Then

PX (x) = PX\e (x) − PX/e (x).

Proof Suppose that e is incident with the vertices v and w. We consider the set
C of all proper colourings of X\e with q colours, and partition it into two parts C1
and C2 as follows: C1 consists of the colourings in which v and w have the same
colour; C2 consists of the colourings in which they have different colours.
If v and w have the same colour, then we may identify them and still have a
proper colouring of G/e. Conversely, any colouring of G/e gives rise to a colour-
ing in the class C1 . So |C1 | = PX/e (q).
If v and w have different colours, then our colouring remains proper when
we re-insert the edge e. Conversely, every proper colouring of X gives rise to a
colouring in the class C2 . So |C2 | = PX (q).
We conclude that PX\e (q) = PX/e (q) + PX (q). Rearranging gives the stated
equality with q substituted for x. But as usual, if this holds for all positive integers
q, it is a polynomial identity.

33
 We can use the argument to prove that the number of proper q-colourings of X
is a monic polynomial of degree n evaluated at q. For both deletion and contraction
reduce the number of edges of the graph, so we can prove the result by induction
on the number of edges. By the induction hypothesis, PX\e is a monic polynomial
of degree n, and PX/e has smaller degree, so the result holds.
Can we use this to evaluate the chronatic polynomial?
In principle, yes, since as remarked, deletion and contraction reduce the num-
ber of edges, so eventually we reach graphs with no edges, and it is clear that
the chromatic polynomial of a graph with n vertices and no edges is xn , since all
colourings are proper!
However, the algorithm is still not very efficient, since each deletion and con-
traction gives us two graphs to consider, so we might have as many as 2|E| graphs
to process.
We can make some short cuts.

Proposition 3.5 • The chromatic polynomial of a complete graph on n ver-

tices is x(x − 1) · · · (x − n + 1); and that of a null graph on n vertices is
xn .
• If X is disconnected, with connected components X1 , . . . , Xc , then

PX (x) = PX1 (x) · · · PXc (x).

• If X is connected, but the removal of a vertex v disconnects it into parts X1

and X2 , and Xi0 = Xi ∪ {v} for i = 1, 2, then

PX (x) = PX10 (x)PX20 (x)/x.

Proof For a complete graph, all colours must be different; for a null graph, there
is no restriction.
The second part is clear since we can colour the components independently.
For the third part, choose a colouring of X10 with q colours. The colouring of
X2 is not independent, since the vertex v must get the same colour as in X10 ; this
0

will be true in a fraction 1/q of all the colourings, since colours can be re-named
arbitrarily.

It is also possible to write down the chromatic polynomials of trees, cycles,

etc. (See the exercises.) Even with all this, the algorithm still takes exponential
time.

34
Example Our earlier example of deletion and contraction shows that

PC4 (x) = PP4 (x) − PK3 (x),

where Cn , Pn , Kn are the cycle, path, and complete graph on n vertices respectively.
We have PK3 (x) = x(x − 1)(x − 2), and it can be shown that PP4 (x) = x(x − 1)3 . So

PC4 (x) = x(x − 1)((x − 1)2 − (x − 2)) = x(x − 1)(x2 − 3x + 3).

Note that PC4 (2) > 0, as we already know.

3.4 Stanley’s Theorem

Here is another, somewhat unexpected, use of the chromatic polynomial.
An orientation of a graph is simply an assignment of directions to the edges
of the graph. An orientation is acyclic if it contains no directed cycles such as
v1 → v2 → . . . → vk → v1 .
We can make a few simple remarks.

• A graph with a loop has no acyclic orientations. [On the other hand, any
loopless graph has acyclic orientations: number the vertices v1 , . . . , vn and
orient any edge from smaller number to greater: vi → v j if i < j.]
• If a graph has multiple edges, then they must all be oriented the same way
in any acyclic orientation; so deleting all but one of them has no effect on
whether there is an acyclic orientation, or on how many there are.

The parallel between these remarks and similar comments about colourings
might lead one to suspect some connection. Indeed there is:

Theorem 3.6 (Stanley’s Theorem) The number of acyclic orientations of a sim-

ple graph X with n vertices is (−1)n PX (−1).

Proof We follow the deletion-contraction proof. Choose an edge e, and consider

the set S of acyclic orientations of X\e.
Observe that every acyclic orientation of X\e can be extended to an acyclic
orientation of X. This could only fail if both choices of orientation of e lead to
directed cycles. But, as the figure shows, this would mean that there was a directed
cycle in X\e:

35
 u -u
>




u

 e
}
Z Z
Z
Z
Zu u
Z ?

Let S be the set of acyclic orientations of X\e. We divide S into two classes:

• S1 is the set of orientations which force the direction of e, because there is

a directed path in some direction between its endpoints.
• S2 consists of orientations in which either ordering of S will be admissible
(will create no directed cycle).

Thus the number of acyclic orientations of X is |S1 | + 2|S2 |.

Moreover, any orientation in the class S2 gives rise to an acyclic orientation
of X/e, since by assumption, identifying the ends of e does not create a directed
cycle. Also |S1 | + |S2 | is the number of acyclic orieintations of X\e.
By induction, we may assume that |S1 | + |S2 | = (−1)n PX\e (−1) and |S2 | =
(−1)n−1 PX/e (−1). So the number of acyclic orientations of X is given by

|S1 | + 2|S2 | = (|S1 | + |S2 |) + |S2 |

= (−1)n PX\e (−1) + (−1)n−1 PX/e (−1)
= (−1)n PX (−1),

and the proof is complete. (In the penultimate line we use the deletion–contraction
formula for the chromatic polynomial of X, namely PX = PX\e − PX/e .)
The induction is on the number of edges, so we start the induction with null
graphs. The null graph on n vertices has chromatic polynomial xn and has a single
acyclic orientation, and (−1)n (−1)n = 1 as required.

Example We found that the chromatic polynomial of a 4-cycle is x(x − 1)(x2 −

3x + 3), and so PC4 (−1) = (−1)(−2)7 = 14. On the other hand, there are 16
orientations of the edges of C4 , of which just two of them fail to be acyclic.

Example The complete graph Kn has n! acyclic orientations, and chromatic

polynomial x(x − 1) · · · (x − n + 1).

36
 We continue with the problem of counting proper colourings of simple graphs.
If you need to solve a problem which involves searching in the space of all graph
colourings, you would like to reduce the size of the space, if you can. We look at
two ways of doing this; one in the remainder of this chapter, and one in the next.

3.5 Colours interchangeable

What is essential about a colouring of a graph is not the individual colours applied
to vertices, but the partition of the vertex set into colour classes.
A partition of the vertex set arises from a colouring if and only if each part of
the partition contains no edges. Can we count partitions with this property, having
a given number (say q) of parts?
Your first thought may be that we count the colourings with q colours, and
then divide by q!, since we don’t care which colour is associated with which part.
But this cannot be correct. For example, the chromatic polynomial of the 4-cycle
is x(x − 1)(x2 − 3x + 3). For q = 4, this is 4.3.7 = 84, which is not divisible by 24.
For q = 5, it is 5.4.13 = 260, but there are no partitions of a set of four vertices
into five parts!
The problem, of course, is that not every colouring with q colours uses all of
the colours, and we should first calculate the number which do, before dividing
by q!. This is a job for Inclusion–Exclusion . . .
Theorem 3.7 Let X be a simple graph with chromatic polynomial PX .
• The number of colourings with q colours, all of which are used, is
 
∗ q−r q
PX (q) = ∑ (−1) PX (r).
r≤q r

• The number of partitions of the vertex set of X into q parts, each part con-
taining no edges, is PX∗ (q)/q!.
Proof Let S be the set of all proper colourings of X with colours c1 , . . . , cq . For
i ∈ {1, . . . , q}, let Ai be the set of colourings in which colour i does not appear. We
want the number of elements of S lying in none of the sets Ai .
If I ⊆ {1, . . . , q} with |I| = i, then i∈I Ai is the set of all colourings using only
T

the colours not in I, so its cardinality is PX (q − i). So by PIE, the number we want
is
q   q  
i q q−r q
∑ (−1) i PX (q − i) = ∑ (−1) r PX (r),
i=0 r=0

37
proving the first part.
For the second part, we obtain the required number of partitions by dividing
the number found in the first part by q!.

Note that PX ∗ is not a polynomial. For PX∗ (q) = 0 for all q > n, and no non-zero
polynomial can have this property!

Example Let X be the 4-cycle. We know that PX (x) = x(x − 1)(x2 − 3x + 3),
so PX (q) = 0, 0, 2, 18, 84 for q = 0, 1, 2, 3, 4. So we find that PX∗ (0) = PX∗ (1) = 0,
PX∗ (2) = 2,

PX (3) = 18 − 3.2 = 12,

PX (4) = 84 − 4.18 + 6.2 = 24,

so the numbers of partitions into q edge-free sets are 0, 0, 2/2 = 1, 12/6 = 2 and
24/24 = 1 for q = 0, 1, 2, 3, 4. These values are easily checked directly.

Exercises
3.1. Let G be a tree (a connected graph with no cycles) on n vertices. Show that
any set of i edges form a subgraph with n − i connected components. Hence show
that the chromatic polynomial of G is q(q − 1)n−1 , independent of the choice of
tree (in other words, it is possible for different graphs to have the same chromatic
polynomial).
Can you prove this (a) directly, (b) by deletion and contraction?
3.2. Use similar reasoning to find the chromatic polynomial of a cycle.
3.3. Suppose that X1 and X2 are graphs, whose vertex sets intersect in a subset of
size r which is a complete graph in each of X1 and X2 . Let X be the union of these
graphs. Prove that

PX (x) = PX1 (x)PX2 (x)/x(x − 1) · · · (x − r + 1).

3.4. Here is an algorithm which takes as input an acyclic orientation of a graph

and outputs a proper vertex colouring. In an acyclic orientation, a vertex v is called
a source if there is no directed edge ending at v.
• Prove that every acyclic orientation of X has a source.

38
Now the algorithm proceeds as follows. Give the first colour c1 to all the sources.
Then remove them; what remains is still acyclic, so give the second colour c2 to
all the sources in this graph. And so on until all vertices have been coloured.

• Show that the output is a proper colouring of the graph.

• Show that the number of colours used by the algorithm lies in the interval
[χ(X), l(X)], where χ(X) is the chromatic number of X and l(X) is the
number of vertices in the longest path contained in X (with no repeated
vertices).
• [Harder] Show that every integer in this range occurs as the number of
colours for some acyclic orientation.

39
4 Graph colouring and symmetry
There are two colourings of a 4-cycle with two colours (red and blue): one pair
of opposite vertices should be red, the other pair blue. There are two reasons why
we might want to regard these two colourings as the same:

• Interchanging the two colours converts one into the other. We discussed
how to cope with this in the last section of the preceding chapter.
• A rotation of the cycle converts one into the other. This is a different idea,
invoking the symmetry of the graph we are colouring. In order to discuss it,
we need a digression through permutation groups and orbit counting.

4.1 A problem from METRO

This problem was in METRO on 20 December 2000. It came in two parts:

Match each of these languages to where they are spoken:

1. Amharic A. Brazil
2. Farsi B. Ethiopia
3. Portuguese C. India
4. Telugu D. Iran
5. Urdu E. Pakistan

This is general knowledge; either you know or you don’t. But the second part
went on to ask:

If the options for this puzzle were given in an entirely random order,
how many of the five pairs of answers would line up correctly in the
same row, averaged over many puzzles? What about if there were ten
options in each column?

This, by contrast, is mathematics; we should be able to work out the answer,

which is in fact 1 (for either question). There are 5! possible arrangements: each of
the five rows will line up correctly under 4! of these. So the answer is 5 · 4!/5! = 1.
In this chapter we will develop a technique which answers this question, and
many others.

40
4.2 Counting up to symmetry
A permutation group on a set X is a group whose elements are permutations of X.
In other words, it is a set of permutations of X which is closed under composition,
contains the identity, and contains the inverse of each of its elements. We write
permutations “on the right”, so that the image of x under permutation g is xg.
[If you have met this before, you may notice that I should really be talking
about the slightly more general concept of a permutation action of a group. In fact
it makes no difference to the counting formulae.]
Given a permutation group G on X, we say that two elements x, y ∈ X are
G-equivalent (and write x ≡G y) if there exists g ∈ G such that xg = y.

Lemma 4.1 G-equivalence is an equivalence relation.

Proof The reflexive, symmetric and transitive laws follow from the identity, in-
verse and composition laws for G:
• If 1 is the identity, then x1 = x, so x ≡G x.

• If x ≡G y, then xg = y for some g; so yg−1 = x, and y ≡G x.

• If x ≡G y, and y ≡G z, then xg = y and yh = z for some g, h ∈ G. Then

x(gh) = z, and gh ∈ G by closure, so x ≡G z.

The equivalence classes of this relation are the orbits of G.

We say that x is fixed by g if xg = x, and write fixX (g) for the number of
elements of X fixed by the permutation g.

Theorem 4.2 (Orbit-counting theorem) Let G be a permutation group on the

finite set X. Then the number of orbits of G on the set X is equal to the average
number of fixed points of its elements, that is,
1
∑ fixX (g).
|G| g∈G

This theorem depends on a group-theoretic result, the Orbit-Stabiliser Theo-

rem. We denote by OrbG (x) the G-orbit containing x. Also, the stabiliser of x is
the set
StabG (x) = {g ∈ G : xg = x}
of elements of G.

41
Theorem 4.3 (Orbit-stabiliser theorem) The stabiliser StabG (x) is a subgroup
of G, and satisfies
| OrbG (x)| · | StabG (x)| = |G|.

The proof that StabG (x) is a subgroup is straightforward; the rest is a refined
version of Lagrange’s Theorem. For each point y ∈ OrbG (x), the set

{g ∈ G : xg = y}

is a coset of StabG (x), and every coset arises in this way.

Proof of the Orbit-counting Theorem We construct a bipartite graph whose

vertex set is X ∪ G, with an edge from x ∈ X to g ∈ G if and only if g fixes x. Now
we count edges in this graph. Each element g lies in fixX (g) edges, so the total
number is
∑ fixX (g).
g∈G

On the other hand, a point x lies in StabG (x) edges. Let O = OrbG (x). Then every
element of O lies in the same number of edges, and so the total number of edges
through points in O is |O| · | StabG (x)| = |G|, by the Orbit-Stabiliser Theorem. So
the total number of edges is |G| times the number of orbits.
Equating the two expressions and dividing by |G| gives the result.

Example: the METRO puzzle The group is the symmetric group S5 , permut-
ing the five countries in the second column. This group obviously has just one
orbit: any country can be moved to any position. If we start with the countries
correctly aligned with the languages, then a country is fixed by a permutation if
and only if, after applying that permutation, the country is still correctly aligned
with the language: so, after a random permutation, the number of pairs lined up
correctly is equal to the number of fixed points of the random permutation. By the
Orbit-counting Lemma, the expected value of this number is equal to the number
of orbits, that is, 1. The same would apply for any number of rows.

Example: Colouring a cube Here is a typical application of the Orbit-counting

Theorem.

42
Problem In how many ways can we colour the faces of a cube with three colours
(say red, green and blue), if we regard two coloured cubes as the same if one is
obtained from the other by a rotation?
This question asks us to count the orbits of the group G of rotations of the cube
on the set S of all 36 ways of applying colours to the faces.
The group G has order 24. It contains the identity; three non-identity rotations
about each of the three “face axes” (joining mid-points of opposite faces); one
non-identity rotation about each of the six “edge-axes” (joining mid-points of op-
posite edges); and two non-identity rotations about each of the four “vertex-axes”
(joining opposite vertices).
A colouring is fixed by a rotation if and only if it is constant on all cycles of
the rotation (acting as a permutation on the six edges of the cube). So the numbers
of fixed colourings are as follows:

• The identity fixes all 36 = 729 colourings.

• A rotation through a half-turn about a face-axis fixes 34 = 81 colourings:

we can choose arbitrarily the colour for the top face, the bottom face, the
east and west faces, and the north and south faces (assuming that the axis
is vertical). A rotation about a quarter turn fixes 33 = 27 colourings, since
all four faces except top and bottom must have the same colour. There are
three half-turns and six quarter-turns.

• A half-turn about an edge-axis fixes 33 = 27 colourings. There are six such

rotations.

• A third-turn about a vertex-axis joining opposite vertices fixes 32 = 9 colour-

ings. There are eight such rotations.

By the Orbit-counting Theorem, the number of orbits is

1
(1 · 729 + 3 · 81 + 6 · 27 + 6 · 27 + 8 · 9) = 57,
24
so there are 57 different colourings up to rotation.

4.3 Orbital chromatic polynomial

The above example leads us into the solution to the problem of counting proper
colourings of a graph up to symmetry. We are given a graph X, and a number q

43
of colours. To increase generality, we assume that we have a group G of automor-
phisms of the graph, which may or may not be the full group of automorphisms.

Theorem 4.4 Given a graph X and a group G of automorphisms of X, there is a

polynomial OPX,G with the property that, for any positive integer q, the evaluation
OPX,G (q) is the number of orbits of G on the set of proper vertex-colourings of G
with q colours. The degree of the polynomial is equal to the number of vertices of
X, and its leading coefficient is 1/|G|.

Proof To apply the Orbit-counting Theorem, we must be able to calculate the

number of colourings of X fixed by any automorphism g ∈ G.
Now g is a permutation of the vertex set of X, and can be decomposed into
disjoint cycles. A colouring is fixed if and only if the colour of the vertices in any
cycle is constant. This means that, if a cycle of g contains an edge of X, there are
no fixed colourings at all.
If no cycle of g contains an edge, we form a new graph X/g by shrinking each
cycle of g to a single vertex. In a natural way, the given fixed colouring gives
rise to a colouring of X/g. Conversely, any proper colouring of X/g lifts to a
proper colouring of X which is constant on the cycles of g. So the number of
fixed colourings of X/g is equal to PX/g (q), the evaluation at q of the chromatic
polynomial of X/g.
We can extend this to all elements g. If a cycle of g contains an edge of the
graph, then we can think of X/g having a loop at the corresponding vertex; and a
graph with a loop has no proper colourings.
Thus we have
1
OPX,G (q) = ∑ PX/g(q).
|G| g∈G
The last statement of the theorem follows. For the element g = 1 has n cycles
(where n is the number of vertices of X, and contributes PX (q) to the sum; any
other element has fewer than n cycles.

Example Consider the 4-cycle, whose automorphism group is the dihedral group
of order 8: there are four rotations, and four reflections.
• If g is the identity, then X/g is equal to the original graph X, whose chro-
matic polynomial is x(x − 1)(x2 − 3x + 3).
• If g is a half-turn, then each vertex is mapped to the opposite vertex, and
X/g is a single edge, with chromatic polynomial x(x − 1).

44
 • If g is a quarter-turn, then the single cycle of g contains edges, so the con-
tribution is zero.
• If g is a reflection in a diagonal, then X/g is a path of length 2, and PX/g (x) =
x(x − 1)2 . There are two such elements.
• If g is a reflection in the horizontal or vertical line, then the cycles of g are
edges, and the contribution is zero.

So
1 1
PX,G (x) = x(x − 1)(x2 − 3x + 3 + 1 + 2(x − 1)) = x(x − 1)(x2 − x + 2).
8 8
Note that PX,G (2) = 1, in agreement with our observation that the two colourings
of X are equivalent up to symmetry. Also PX,G (3) = 6: can you describe the six
3-colourings up to symmetry?

4.4 What we can’t yet do

We started this chapter with two ways to reduce the count of colourings of a graph:
count partitions into edge-free sets rather than colourings; and count colourings
up to some prescribed symmetry. We saw at the end of the last chapter how to do
the first, and in this chapter how to do the second, of these reductions. Can we
combine them, that is, can we find a way to count partitions into edge-free sets up
to symmetry?
We can use the inclusion-exclusion technique of the last chapter to count q-
colourings in which all colours actually appear, up to a given group G of automor-
phisms. But we cannot simply divide the answer by q!. For it might happen that
some re-colouring by changing the numbering of the colours can also be realised
by a symmetry of the graph.
There is currently no known solution of this problem, apart from constructing
the partitions and their orbits under the group explicitly, which is likely to be very
slow for large graphs!

4.5 Example: the Petersen graph

The Petersen graph is probably the most famous graph of all. Introduced by the
Danish mathematician in 1898, to show that a certain strategy for proving the
Four-Colour theorem would not work, it has many remarkable properties, and

45
occurs as an example or counterexample all over group theory. There is a whole
book devoted to it, written by Derek Holton and John Sheehan (the latter a lecturer
at Aberdeen for many years).

v
ZZ
 Z
 Z
 Z
v
 Z

v Zv
 Z

P  B 
B P PPv  B
v
   
B Z  B  
B Z  B  
Z
 B 
B
 Z  B

v v
B Z
B 
 Z B 
B  S 
 S 
v Sv
B
B

The most convenient abstract representation of it is as follows. The vertices

can be identified with the ten 2-element subsets of {1, 2, 3, 4, 5}; two vertices are
joined by an edge if and only if the corresponding subsets are disjoint. (As an
exercise, label the above figure to demonstrate this.)
This shows that the symmetric group S5 of order 120 acts as a group of auto-
morphisms of the graph, permuting the labels in the obvious way. In fact this can
be shown to be the full automorphism group of the graph.
The chromatic polynomial of the Petersen graph can be shown to be
PX (q) = q(q − 1)(q − 2) ×
(q7 − 12q6 + 67q5 − 230q4 + 529q3 − 814q2 + 775q − 352).
In particular, PX (3) = 120, showing that the Petersen graph has chromatic num-
ber 3 (in agreement with Brooks’ Theorem). In fact, the 120 colourings with 3
colours are all equivalent (up to permuting the labels 1, . . . , 5 and re-numbering
the colours) to the one in which vertices 12, 13, 14 and 15 are given colour c1 , 23,
24, and 25 get colour c2 , and 34, 35, and 45 get colour c3 .
Evaluating the polynomial gives the following table of numbers of q-colourings
for q = 3, . . . , 10:
q 3 4 5 6 7 8 9 10
PX (q) 120 12960 332880 3868080 27767880 144278400 594347040 2055598560

46
 Using our inclusion-exclusion formula to find the number of colourings in
which all colours are used, and dividing by q!, we find the following table of
numbers of partitions into q edge-free parts:

q 3 4 5 6 7 8 9 10
PX∗ (q)/q! 20 520 2244 2865 1435 315 30 1

Now consider the orbit-counting version. We can examine the types of element
of the symmetric group S5 , and figure out which ones have the property that no
cycle of the permutation on vertices contains an edge. This applies only for the
identity, the 10 transpositions, and the 20 cycles of length 3. (For example, the
permutation (1, 2, 3)(4, 5) has the property that adjacent vertices 14 and 25 lie in
the same cycle (14, 25, 34, 15, 24, 35) for its action on vertices.) The contracted
graphs for a 2-cycle and a 3-cycle are shown:

u u u

u u u u u
@ @ @
@ @ @
@u @u @u

It is not hard to calculate the chromatic polynomial of each of these. We find

that the orbital chromatic polynomial of the Petersen graph is

OPX,G (q) = q(q − 1)(q − 2) ×

(q7 − 12q6 + 67q5 − 220q4 + 469q3 − 664q2 + 595q − 252)/120.

and the values for from 3 to 10 colours are

q 3 4 5 6 7 8 9 10
OPX,G (q) 6 208 3624 36654 248234 1254120 5089392 17449788

As noted earlier, we don’t have a simple method to calculate the numbers of

orbits of S5 on partitions into edge-free sets. I computed them directly and got the
†
following results, using OPX,G (q) for the numbers obtained:

q 3 4 5 6 7 8 9 10
†
OPX,G (q) 1 10 30 36 20 7 1 1

47
The value for q = 3 is 1, corresponding to our statement that there is “essentially”
only one way to 3-colour the vertices (up to colour renaming and graph symme-
try). Similarly, the entry 1 for q = 9 arises because an edge-free partition with
nine parts must consist of a non-edge and eight single vertices, and all non-edges
are equivalent up to symmetry of the graph.
Notice how much smaller these numbers are!

Exercises
4.1. This question is Enigma 1124 from New Scientist. It can be solved by a few
applications of the Orbit-counting Lemma, or more easily by a technique we’ll
see later, the Cycle Index Theorem.
A stained glass window consists of nine squares of glass in a 3 × 3 array. Of
the nine squares, k are red, the rest blue. A set of windows is produced such that
any possible window can be formed in just one way by rotating and/or turning over
one of the windows in the set. Altogether there are more than 100 red squares in
the set. Find k.
4.2. A permutation group G on a set X is called transitive if it has only one orbit
on X.
Show that, if |X| > 1 and G is transitive on X, then G contains a derangement
(a permutation with no fixed points). [What is the average number of fixed points
of elements of G?]
4.3. Some problems on the Petersen graph. The diameter of a graph is the
maximum number of steps in a shortest path between any two vertices; the girth
is the number of edges in a shortest cycle; and we say that a graph has valency
at least (resp., at most) k if every vertex is incident with at least (resp., at most) k
edges.

• Show that the group of all automorphisms has order 120 (and hence is the
group S5 given earlier).
• Show that a graph with valency (at most) 3 and diameter (at most) 2 has at
most ten vertices, with equality if and only if it is isomorphic to the Petersen
graph.
• Show that a graph with valency (at least) 3 and girth (at least) 5 has at least
ten vertices, with equality if and only if it is isomorphic to the Petersen
graph.

48
 • Show that it is impossible to colour the edges of the Petersen graph with
three colours in such a way that no two edges with the same colour meet at
a vertex.

4.4.

• Verify the formula given for the chromatic polynomial of the Petersen graph.
• Verify the graphs X/g given for the Petersen graph and construct their chro-
matic polynomials.

4.5. Show that, if X is the null graph on n vertices (the graph with no edges) and
G is the symmetric group Sn , then
 
q+n−1
OPX,G (q) = .
n

[You might like to match the colourings up with samples, under appropriate rules,
of n things from a set of q.]

49
5 Matroids
The notion of linear independence of a family of vectors in a vector space satis-
fies two simple conditions (namely, a subfamily of a linearly independent family
is linearly independent, and the well-known exchange property for maximal in-
dependent sets), from which most of its familiar properties hold: the existence
and constant size of bases, the rank and nullity theorem, etc. These properties
crop up in various other situations. Indeed, the exchange property is credited to
Steinitz who observed it for the notion of algebraic independence of elements in
a field over an algebraically closed subfield. This leads to the concept of the tran-
scendence degree of a field extension. Furthermore, subsets of the edge set of a
graph which induce acyclic graphs (forests), and subfamilies of families of sets
possessing systems of distinct representatives, also satisfy these conditions.
The underlying abstract structure was given the name “matroid” by Whitney
(a generalisation of “matrix”). Tutte observed that a two-variable generalisation
of the chromatic polynomial of a graph could also be extended to this setting; this
is the Tutte polynomial of the matroid. In this chapter and the next, we provide a
brief introduction to these concepts.

5.1 Definition and examples

We want to write down simple conditions satisfied by the collection of linearly
independent sets in a vector space. Whitney came up with the following definition.
A matroid M on E is a pair (E, I ), where E is a finite set, and I is a non-
empty family of subsets of E (whose elements are called independent sets) with
the properties

(a) if I ∈ I and J ⊆ I, then J ∈ I ;

(b) (the exchange property) if I1 , I2 ∈ I and |I1 | < |I2 |, then there exists w ∈ I2 \I1
such that I1 ∪ {w} ∈ I .

Let us check that these properties do hold for linearly independent sets of
vectors. The first property is clear. Suppose that the second property fails. Then
for every vector w ∈ I2 , the set I1 ∪ {w} is linearly dependent; so w is a linear
combination of vectors in I1 . Let I1 = {v1 , . . . , vr } and I2 = {w1 , . . . , ws }, where
s > r. Suppose that
r
wi = ∑ ai j v j for i = 1, . . . , s.
j=1

50
Then A = (ai j ) is an s × r matrix, so there are scalars c1 , . . . , cs , not all zero, such
that
s
∑ ciai j = 0 for j = 1, . . . , r.
i=1
(This is just the statement that a system of homogeneous linear equations, with
more unknowns than equations, has a non-zero solution.) Putting the displayed
equations together we find that
s
∑ ciwi = 0,
i=1

contradicting the linear independence of I2 .

A matroid whose independent sets are the linearly independent subsets of a
family of vectors is called a vector matroid.
Note that we speak of a family rather than a set of vectors here, since the same
vector may occur more than once. (Any family containing a repeated vector is to
be regarded as linearly dependent.) If we think of the vectors as the n columns
of a matrix, we can regard the set E of elements of the matroid as the index set
{1, 2, . . . , n} for the columns; then a subset I of E is independent if and only if the
family of columns with indices in I is linearly independent.
If this seems a little confusing, here is an example. Consider the vectors

v1 = (1, 0) = v2 , v3 = (1, 1) = v4 , v5 = (0, 0).

The corresponding vector matroid (E, I ) has E = {1, 2, 3, 4, 5} and

I = {0,
/ {1}, {2}, {3}, {4}, {1, 3}, {1, 4}, {2, 3}, {2, 4}}.

More formally, a representation of a matroid (E, I ) over a field F is a map

χ from E to an F-vector space with the property that a subset I of E belongs to
I if and only if χ(I) is linearly independent. Two representations χ, χ 0 of M are
equivalent if there is an invertible linear transformation of V whose composition
with χ is χ 0 .
We will frequently meet the special case where E consists of all the vectors in
an n-dimensional vector space over GF(q). This will be referred to as the complete
vector matroid, and denoted by V (n, q).
As referred to in the introduction, the following are also examples of matroids:

51
 (a) The uniform matroid Un,r of rank r on n points is the matroid (E, I ), where
|E| = n and I consists of all the subsets of E of cardinality at most r. In the
case r = n, we have the free matroid of rank n, denoted by Fn : every subset
is independent.

(b) Let E be a finite family of elements in a vector space, and J the set of affine
independent subfamilies. (A family (v j : j ∈ J) is affine independent if the
relation ∑ c j v j = 0, where c j are scalars with ∑ c j = 0, implies that c j = 0
for all j.) Then (E, J ) is a matroid. Such a matroid is called affine.

(c) Let K be an algebraically closed field containing an algebraically closed sub-

field F. Let E be a finite family of elements of K, and J the set of all
subfamilies of E which are algebraically independent over F. Then (E, J )
is a matroid. Such a matroid is called algebraic.

(d) Let G = (V, E) be a finite graph (loops and multiple edges are allowed). Let
J be the set of all subsets A of E for which the graph (V, A) is acyclic (that
is, a forest). Then (E, J ) is a matroid. Such a matroid is called graphic,
and is denoted by M(G).

(e) Let (Xe : e ∈ E) be a family of sets. Let J be the family of all subsets I ⊆ E
for which the subfamily (Xe : e ∈ I) possesses a transversal (that is, there is
a family (xe : e ∈ I) of distinct elements such that xe ∈ Xe for all e ∈ I). Then
(E, J ) is a matroid. Such a matroid is called transversal.

Class (d), graphic matroids, are of special importance, and we devote a section
to them later.

5.2 Properties of matroids

Bases
It follows from the second axiom that all maximal independent sets in a ma-
troid M have the same cardinality k, called the rank of M. These maximal inde-
pendent sets are called the bases of M. It is possible to recognise when a family
B of subsets of E consists of the bases of a matroid on E. This is the case if and
only if

(a) no element of B properly contains another;

52
 (b) if B1 , B2 ∈ B and y ∈ B2 \ B1 , then there exists x ∈ B1 \ B2 such that B1 \
{x} ∪ {y} ∈ B. (This property is also referred to as the exchange property.)
The bases of a vector matroid are just the subsets which index sets of vectors
which are bases for the space spanned by all the vectors (hence the name).
The bases of a uniform matroid Un,r are all the subsets of E of cardinality r.

Rank
We can extend the definition of rank to all subsets of E: the rank ρA of an
arbitrary subset A of E is the cardinality of the largest independent set contained
in A. It is also possible to recognise when a function ρ from the power set of a
set E to the non-negative integers is the rank function of a matroid. (Again, the
exchange property shows that any two maximal independent subsets of A have the
same cardinality.)
In a vector matroid, the rank of a subset is the dimension of the subspace
spanned by its vectors. In a graphic matroid on n vertices, if the edges of A form
a graph with r components, then the rank of A is n − r.
In the uniform matroid Un,r , the rank of a subset A is given by

|A| if |A| ≤ r,
ρ(A) =
r if |A| ≥ r.
Finally, we calculate the rank function of the dual of a matroid M.
Proposition 5.1 Let M be a matroid on E with rank function ρ. Then the rank
function ρ ∗ of the dual matroid M ∗ is given by
ρ ∗ (A) = |A| + ρ(E \ A) − ρ(E).
Proof If A is independent in M ∗ , then it is contained in a basis B, and so E \ A
contains a basis E \ B for M. Then
ρ(E) = ρ(E \ B) ≤ ρ(E \ A) ≤ ρ(E),
so the second and third terms on the right cancel, and we have ρ ∗ (A) = |A|.
Conversely, if ρ ∗ (A) = |A|, then ρ(E \ A) = ρ(E), and so E \ A contains a
basis for M; hence A is contained in a basis for M ∗ , and is independent.
Thus the formula correctly identifies the independent sets as those sets A with
∗
ρ (A) = |A|.
The remaining step, showing that ρ ∗ (A) is equal to the size of a maximal
independent set of M ∗ contained in A, is an exercise.

53
Duality
The set of all complements of bases of M is the set of bases of another matroid
M ∗ on E, called the dual of M.
This is most easily proved by showing that conditions (a) and (b) above for a
family B of sets imply the same condition for the family of complements.
The dual of a vector matroid is a vector matroid over the same field: we
will postpone this until we are dealing with the connection between matroids and
codes.
The bases of the uniform matroid Un,k are all the sets of cardinality k; their
complements are all the sets of cardinality n − k. Thus, the dual of Un,k is Un,n−k .

Other notions
A flat in a matroid M = (E, J ) is a subset F of E with the property that
ρ(F ∪ {x}) = ρF + 1 for all x ∈ E \ F. If ρF = k and A is an independent subset
of F of cardinality k, then F = {x ∈ E : ρ(A ∪ {x}) = ρA}. A flat whose rank is
one less than that of E is called a hyperplane.
The flats of a matroid form a lattice (in which the meet operation is intersec-
tion), which is atomic and submodular; these properties of a lattice ensure that it
arises as the lattice of flats of a matroid.
There are many other equivalent ways of defining matroids: via circuits, co-
circuits, flats, hyperplanes, etc. We do not pursue this here.
Let M = (E, J ) be a matroid of rank r, and let k be a non-negative integer
with k ≤ r. The truncation of M to rank k is the matroid on E whose family of
independent sets is
Ik = {I ∈ I : |I| ≤ k}.
The flats of the truncation are all the flats of rank less than k of the original matroid
together with the whole set E.

5.3 Graphic matroids, planarity and duality

Recall that in a graphic matroid based on a graph X, the element set E is the edge
set of the graph, and a set of edges is independent if it contains no cycle.
We begin by verifying the matroid axioms for graphic matroids. If I is a set
of edges containing no cycle, and J ⊆ I, then clearly J contains no cycle. So let
us suppose that I1 and I2 are acyclic sets of edges, with |I2 | > |I1 |. We use the
following fact (easily verified by induction):

54
Proposition 5.2 A graph containing no cycles, which has n vertices and m edges,
has n − m connected components.

Now, regard I1 and I2 as edge sets of acyclic graphs on the same vertex set.
Since |I2 | > |I1 |, the Proposition implies that I1 has more connected components
than I2 . So the edges of I2 cannot all be contained within connected components
of I1 ; at least one of them must join vertices in different connected components of
I1 . Adding this edge to I1 cannot create a cycle. So the exchange property holds.
In a graphic matroid, a set consisting of a single edge has rank 0 if the edge
is a loop, or 1 otherwise. A set consisting of two non-loops has rank 1 if the two
edges have the same vertices, and rank 2 otherwise. Thus, in the cycle matroid
corresponding to a simple graph, any set of cardinality at most 2 is independent.
Our example of a vector matroid above is also graphic, as the following picture
shows:
e
.........1
........... ...........
e
.........3
........... ...........
e5
u u u u u
..... ...... ...... ..... ......
...... .... ...... .... ..... ......
.......
.....
........ .....
.. .....
........ .....
.. ..... .....
.......................... .......................... ......
e2 e4

Proposition 5.3 Let X be a graph, and v and w vertices lying in different con-
nected components. Then the graph X 0 obtained by identifying the vertices v and
w has the same cycle matroid as X.

This is because the operation described preserves edges and neither creates
nor destroys any cycles. Thus another graph whose cycle matroid is the earlier
example is shown in the following figure:
e1 ..........
e3
..........
.......... ................ ............... ................ .............
e5
u ......
......
.......
u ........
.
... ...
u
........ ..
.
... .... .
.
.................................. ........................................ ............
. .
e2 e4

Not every matroid is graphic. Indeed, the dual of a graphic matroid is not
necessarily graphic. Here is an example. Let M be the graphic matroid obtained
from the complete graph K5 . This graph is connected, with five vertices and ten
edges; so |E| = 10 and M has rank 4. The dual matroid M ∗ has rank 6.
Suppose that M ∗ were graphic, obtained from a connected graph X. Then X
has seven vertices and ten edges. Since 2 · 10 < 3 · 7, there is a vertex of X which
lies on at most two edges. I will deal with the case where v is on two edges e1 and
e2 ; the other case is easier and is left to you.

55
 A spanning tree of X must have at least one edge through the vertex v; so every
base of M ∗ has one or both of e1 and e2 . This means that no base of M contains
both e1 and e2 . But, in the complete graph K5 , it is easy to see that any two edges
lie in some spanning tree. So we have a contradiction.
There is an important class of graphs for which the dual of the graphic matroid
is also graphic: this is the class of planar graphs, those which can be drawn in the
plane without crossing edges. We will explore this class a little.
A planar graph has faces, which can be defined as follows. Note that the edges
at any vertex have a cyclic order. Start along an edge; on reaching a vertex, take
the rightmost edge; continue until we return to the starting point. Usually, we have
traced a simple closed curve in the plane, which has an inside and an outside. If
one of these two regions contains no further vertices of the graph, then it is a face.
This doesn’t always work: here are three examples.

r
r r r r
 rT
T
T T T T
 T  T  T T  T  T
r
 Tr r Tr   T T r Tr r Tr
r
  Tr T
r
 Tr

In the first graph, the interior of each triangle is a face, but the exterior is not
a face, since it contains the other triangle. The second example has the same bad
property, but it is the interior of the large triangle that fails to be a face. In the
third case, the boundary of the exterior face is not a simple closed curve.
I don’t have time to discuss the topological niceties in detail: the philosopher
of mathematics Imre Lakatos wrote a book devoted to this example. Let us just
say a planar graph is “good” if, when we regard the graph as projected onto a
sphere, every face is homeomorphic to a disc. The first two graphs above are not
“good”, since in each case one face has a hole; the third is good.

Theorem 5.4 (Euler’s formula) If a good planar graph has V vertices, E edges,
and F faces, then
V − E + F = 2.

The first two graphs in our picture above have V = 6, E = 6, F = 3, and so fail
to satisfy the formula; the third has V = 6, E = 7, F = 3.
Here are outlines of two proofs.

56
First proof The first proof is by induction. Remove something and make a
simpler graph. But this graph may not be good, so there are problems. The best
approach is to show that there is always a vertex whose removal leaves a good
graph. This removal reduces the numbers of vertices, edges and faces by 1, m
and m − 1 respectively (m faces are destroyed and one new one created), so the
inductive step works. The induction starts with a one-vertex graph having, say, m
loops, where V = 1, E = m, and F = m − 1.

Second proof This proof is more complicated but the techniques lead to impor-
tant ideas in homological algebra. We start by giving an orientation to each edge,
and an orientation (a “positive direction of rotation” to each face. Now define
vector spaces over Q by
V−1 = Q, V0 = QV, V1 = QE, V2 = QF, V3 = Q,
where for example QE means a vector space whose basis is identified with E.
Define linear maps δi : Vi → Vi−1 by the rules
• δ0 maps every vertex to 1;
• δ1 maps the oriented edge e = (v, w) to w − v;
• δ2 maps the oriented face F to the sum of the edges around the boundary of
F, with + sign if the orientation of the edge agrees with that of the face, −
otherwise;
• δ3 maps 1 to the sum of the faces.
Now show that the sequence
0δ 1 δ 2 3 δ δ
V−1 ←V0 ←V1 ←V2 ←V3

is exact, in the sense that the kernel of each map is the dimension of the next. It
follows that the alternating sum of the dimensions of the vector spaces is zero,
that is, 1 −V + E − F + 1 = 0, as required.
Now let X be a connected planar graph. The corresponding graphic matroid
has E elements and rank |V | − 1. Its dual has E elements and rank |F| − 1 (from
Euler’s formula), so it is natural to suppose that we can take its faces as the vertices
of the dual graph. Indeed we can! Join two faces on opposite sides of an edge e
with a “dual” edge e∗ ; this gives a graph whose edges are naturally bijective with
those of X. It can be shown that the graphic matroids of these two graphs are
indeed duals.

57
Example The example shows that the dual of the complete graph K4 is again
K4 .
u
SS
 S
S 
 S ................................ ............
.......... .....................
.......... ..... ......
 u ........
uS
........
....... .... .... .......
..
........ .. ... ......
......
....
... ....
...
u
 J ..
S ....
. ...
.... ...
...
 
J HH S ...
... ...
...
...   H S ...
...  J H ...
... ...
...
...   JJu H HHSS ...
...
...   ...
...
u Su
..
..
...
..
..

 HH ..
..
... ..
... ....
... ...
...
... ..
..
u ...
....
....
...... ..
...
... ......
.
. .
... ........... .
.......
......... ........ ....
........... ........
.........
.......... .......
.............. .......... ............ .......
.............................................................. ................ .........
..............................................

Exercises
5.1. In this exercise, we prove that a graphic matroid is representable over any
field.
Let G = (V, E) be a graph, where V = {v1 , . . . , vn } and E = {e1 , . . . , em }.
Choose arbitrarily an orientation of each edge ei (that is, the edge ei has an initial
and a terminal vertex, which may be the same). Now construct an n × m matrix
A = (ai j ) as follows:

+1 if e j is a non-loop with terminal vertex vi ;

(
ai j = −1 if e j is a non-loop with initial vertex vi ;
0 otherwise.
Prove that, given any cycle in the graph, the sum of the columns corresponding
to the edges in the cycle (with signs ±1 chosen appropriately) is zero. Prove also
that if a set of edges contains no cycle, then there is a row containing a single
non-zero entry in the corresponding columns.
Hence show that, for any field F, a set of columns of A is linearly indepen-
dent over F if and only if the corresponding set of edges of G forms an acyclic
subgraph.
5.2. What are the bases, the flats, the hyperplanes, and the rank function of the
uniform matroid Un,r ? What is the dual of this matroid?

58
5.3. Prove that the matroid U4,2 is not graphic.
5.4. Let M be a graphic matroid arising from a connected graph G = (V, E) on n
vertices. Prove that the rank function is given by

ρA = n − κ(A),

where κ(A) is the number of connected components of the graph (V, A).
5.5. Let M(G) be a graphic matroid, where the graph G = (V, E) is connected.
Show that a set A ⊆ E is independent in M(G)∗ if the removal of A does not
disconnect G.

59
6 Tutte polynomial
In this chapter, after looking at one more construction which matroid theory has
inherited from graph theory, we introduce the Tutte polynomial of a matroid and
examine some of its properties.

6.1 Deletion and contraction

The roots of matroid theory in graph theory explain much of the terminology used.
For example, the use of the letter E for the set of elements of a matroid arises from
its use as the edge set of a graph. In this section, we will meet loops, deletion and
contraction, all of which are more transparent for graphic matroids.
Let M = (E, I ) be a matroid. The element e ∈ E is called a loop if {e} ∈ / I,
or equivalently, if ρ({e}) = 0. In a graphic matroid, e is a loop if and only if it
is a loop of the underlying graph. Thus, an element is a loop if and only if it is
contained in no basis.
The element e ∈ E is a coloop if it is a loop in the dual matroid M ∗ . Thus, e
is a coloop if and only if it is contained in every basis of M; that is, ρ(A ∪ {e}) =
ρ(A) + 1 whenever e ∈ / A. In a graphic matroid, e is a coloop if and only if it is
a bridge, an element whose removal increases by one the number of connected
components.
Let e be an element which is not a coloop. The deletion of E is the matroid
M\e on the set E \ {e} in which a subset A is independent if and only if it is
independent in M (and doesn’t contain e). There is no compelling reason to forbid
the deletion of coloops, but it makes the theory tidier – see the next paragraph.
In a graphic matroid, deletion of e corresponds to deletion of the edge e from the
graph.
Let e be an element which is not a loop. The contraction of e is the matroid
M/e on the set E \ {e} in which a set A is independent if and only if A ∪ {e} is
independent in M. (Here it is clear that contracting a loop would make no sense, so
our earlier restriction will preserve duality.) In a graphic matroid, contraction of e
corresponds to contraction of the edge e, that is, identifying the vertices forming
the two ends of e.

Proposition 6.1 Let e be an element of the matroid M which is not a loop. Then
e is not a coloop of M ∗ , and

(M/e)∗ = M ∗ \e.

60
Proof Bases of M ∗ \e are bases of M not containing e, whose complements are
bases of M/e (together with e.
Deletion and contraction form the basic inductive method for studying ma-
troids, as we will see.

6.2 The Tutte polynomial

Let M be a matroid on the set E, having rank function ρ. The Tutte polynomial of
M is most easily defined as follows:
TM (x, y) = ∑ (x − 1)ρ(E)−ρ(A)(y − 1)|A|−ρ(A).
A⊆E

Bill Tutte, who began his career as a chemist – and was also one of the most
famous of the Bletchely Park codebreakers – originally called his polynomial the
“dichromate” of the graph (since it is a two-variable version of the chromatic
polynomial).
For example, the Tutte polynomial of the uniform matroid Ur,n is
r   n  
n r−i n
TUn,r (x, y) = ∑ (x − 1) + ∑ (y − 1)i−r ,
i=0 i i=r+1 i

since a set A of cardinality i ≤ r satisfies ρ(E) − ρ(A) = r − i and |A| − ρA = 0,

while a set A of cardinality i ≥ r + 1 satisfies ρ(E) − ρ(A) = 0 and |A| − ρ(A) =
i − r.
In particular, if M is the free matroid, with every set independent (equivalently,
every element is a coloop), then
n  
n
TM (x, y) = ∑ (x − 1)n−i = xn .
i=0 i
Similarly, if only the empty set is independent (equivalently, every element is a
loop), then TM (x, y) = yn .
The appearance of the terms x − 1 and y − 1 in the polynomial is a historical
accident. Tutte defined his polynomial by a completely different method, depend-
ing on the choice of an ordering of the elements of the matroid, but giving a result
independent of the ordering. Meanwhile, the rank polynomial of M was defined
as
RM (x, y) = ∑ xρ(E)−ρ(A) y|A|−ρ(A) .
A⊆E

61
Henry Crapo showed that in fact TM (x, y) = RM (x − 1, y − 1).
A number of simple matroid invariants can be extracted from the Tutte poly-
nomial, as the next result shows. The proof is an exercise.

Proposition 6.2 Let M be a matroid on n elements.

(a) The number of bases of M is equal to TM (1, 1).

(b) The number of independent sets of M is equal to TM (2, 1).

(c) The number of spanning sets of M is equal to TM (1, 2).

(d) TM (2, 2) = 2n .

Calculation of the Tutte polynomial is possible by an inductive method using

deletion and contraction, as follows.

Theorem 6.3 (a) T0/ (x, y) = 1, where 0/ is the empty matroid.

(b) If e is a loop, then TM (x, y) = yTM\e (x, y).

(c) If e is a coloop, then TM (x, y) = xTM/e (x, y).

(d) If e is neither a loop nor a coloop, then

TM (x, y) = TM\e (x, y) + TM/e (x, y).

Proof (a) is trivial. For the other parts, we note that each subset A of M/e or M\e
corresponds to a pair of subsets A and A ∪ {e} of M. let M 0 = M\e and M 00 = M/e
(where appropriate), and use ρM , ρM0 and ρM 00 for the rank functions of the three
matroids M, M 0 , M 00 , and E 0 = E 00 = E \ {e}.
If e is a loop, then we have

ρM (E) = ρM 0 (E 0 ),
ρM (A) = ρM (A ∪ {e}) = ρM0 (A),
|A ∪ {e}| = |A| + 1, |E| = |E 0 | + 1.

Thus the two terms in the sum for T (M) are respectively 1 and y − 1 times the
term in T (M 0 ) corresponding to A, and so (b) holds.
The other two parts are proved similarly.

62
 The Tutte polynomials of a matroid and its dual are very simply related:
Proposition 6.4

TM∗ (x, y) = TM (y, x).

Proof Let A be a subset of E and let E ∗ = E and A∗ = E \ A. If ρM and ρM ∗ are

the rank functions of M and M ∗ respectively, we have

|A∗ | − ρM ∗ (A∗ ) = ρM (E) − ρM (A),

ρM ∗ (E ∗ ) − ρM∗ (A∗ ) = |A| − ρM (A).

(See Proposition 5.1 in the preceding chapter.) So the term in TM∗ arising from A∗
is equal to the term in TM arising from A but with x and y interchanged.

The Tutte polynomial has a number of other properties. For example, we say
that the matroid M is the direct sum of two matroids M1 and M2 if its ground set E
is the disjoint union of the ground sets E1 and E2 of the matroids M1 and M2 , and
the independent sets of M are all those sets of the form I1 ∪ I2 , where I1 and I2 are
independent sets of M1 and M2 respectively. Now it is easy to show the following:

Proposition 6.5 If M = M1 ⊕ M2 , then TM (x, y) = TM1 (x, y) · TM2 (x, y).

A remarkable converse of this result was proved recently by Merino, de Mier

and Noy:

Theorem 6.6 If the matroid M is indecomposable (that is, it is not isomorphic to

the direct sum of non-empty matroids), then its Tutte polynomial is irreducible.

6.3 Tutte polynomial and chromatic polynomial

As an illustration of the use of the inductive method, we consider the chromatic
polynomial of a graph X, the polynomial PG with the property that PX (q) is equal
to the number of proper q-colourings of X. We show that PX (q) is the evaluation
of the Tutte polynomial of M(X) at x = 1 − q, y = 0, multiplied by a prefactor
depending on the numbers of vertices and connected components of X.

63
Corollary 6.7 Let X = (V, E) be a graph. Then

PX (q) = (−1)ρ(X) qκ(G) TM(X) (1 − q, 0),

where κ(X) is the number of connected components of G and ρ(X) + κ(X) the
number of vertices.

Proof The matroid M(X) associated with X has rank ρ(E) = n − κ(X), where n
is the number of vertices. Let q be any positive integer.
The chromatic polynomial satisfies the following recursion:
(a) If X has n vertices and no edges, then PX (q) = qn .

(b) If X contains a loop, then PX (q) = 0.

(c) If e is an edge which is not a loop, then

PX (q) = PX\e (q) − PX/e (q),

where X\e and X/e are the graphs obtained from X by deleting and con-
tracting e, respectively.
Here (a) is clear since any vertex-colouring of the null graph is proper; and (b)
is trivial. For (c), as we saw in part 3 of the notes, if e has vertices v and w, the
proper colourings c of X\e can be divided into two classes:
(a) those with c(v) 6= c(w), which yield proper colourings of G;

(b) those with c(v) = c(w), which yield proper colourings of G/e.
Now we show by induction on the number of edges that

PX (q) = (−1)ρ(X) qκ(X) TM(X) (1 − q, 0).

This is clear when there are no edges since ρ(X) = 0, κ(X) = n and TM(X) = 1.
It is also clear if there is a loop, since TM(X) (x, 0) = 0 in that case by part (b) of
Theorem 6.3. If e is a coloop then deletion of e increases κ by 1 and decreases ρ
by 1; also PX\e (q) = qPX (k)/(q − 1), since a fraction (q − 1)/q of the colourings
of X\e will have the ends of e of different colours. So the inductive step is a
consequence of part (c) of Theorem 6.3.
Finally, if e is neither a loop nor a coloop, use (c) above and (d) of Theo-
rem 6.3.

64
 We can give an alternative proof of this result, which is more direct, using
our inclusion-exclusion formula for the chromatic polynomial in Chapter 3 of the
notes:
PX (q) = ∑ (−1)|A| qκ(A) ,
A⊆E

where κ(A) is the number of connected components of the graph with edge set A.
(We called this c(A) in Chapter 3.)
Let n be the number of vertices. Then we have ρ(A) = n − κ(A), and so

(−1)ρ(X) q−κ(X) PX (q) = ∑ (−1)|A|+ρ(X)qκ(A)−κ(X)

A⊆E

= ∑ (−1)|A|−ρ(A)(−1)ρ(X)−ρ(A)qρ(X)−ρ(A)
A⊆E

= ∑ (−q)ρ(X)−ρ(A)(−1)|A|−ρ(A)
A⊆E
= TM(X) (1 − q, 0).

(We use the fact that ρ(A) + κ(A) = n = ρ(X) + κ(X), so κ(A) − κ(X) = ρ(X) −
ρ(A).) Multiplying by (−1)ρ(X) qκ(X) gives the result.

Example Suppose that X is a tree with n vertices. Then the graphic matroid
M(X) is the free matroid, with every set independent (equivalently, every element
is a coloop); and so TM(X) (x, y) = xn . Thus

PX (q) = (−1)n−1 q(1 − q)n−1 = q(q − 1)n−1 .

Example Let X be the n-cycle graph. Every set of edges except the whole set
E is independent; so M(X) is the uniform matroid Un,n−1 . So we can write down
the Tutte polynomial, and hence the chromatic polynomial of X (see exercise 6.3
below).

Exercises
6.1. For which values of n and r is the uniform matroid Un,r graphic?
6.2. Construct

(a) non-isomorphic graphs X1 , X2 for which the graphic matroids are isomorphic;

65
 (b) non-isomorphic graphic matroids M(X1 ), M(X2 ) which have the same Tutte
polynomial [Hard!].

6.3. Let X be the n-cycle graph. Find the chromatic polynomial of X

(a) by first finding the Tutte polynomial of M(X), as suggested in the text;
(b) by deletion and contraction (you will have to use induction).

66
7 Matroids and codes
There is a very close correspondence between linear codes, on one hand, and ma-
troids (specifically, representations of matroids) on the other – the two types of
structure correspond exactly, up to the natural definition of equivalence in each
case. Among other things, this correspondence leads us to the theorem of Curtis
Greene, showing that the weight enumerator of a code is a specialisation of the
Tutte polynomial of the corresponding matroid. This then provides a combinato-
rial proof of MacWilliams’ Theorem on the weight enumerators of dual codes.

7.1 The correspondence

Let A be a k × n matrix over a field F, satisfying the condition that the rows of A
are linearly independent, so that the row space of A has dimension k.
There are two different structures that can be built from A.
First, the row space of A is an [n, k] code over F, that is, a k-dimensional
subspace of F n . Now row operations on A simply change the basis for the code,
leaving the actual code completely unaltered. Column permutations replace the
code by an “equivalent” code. (The same is true of the operation of multiplying
a column by a non-zero scalar in F, an operation we didn’t consider before; like
column permutations, it alters the code but doesn’t change linearity, dimension,
or distances.)
Second, there is a matroid M on the set E = {1, 2, . . . , n}, in which a set I is
independent if and only if the family of columns of A whose indices belong to
I is linearly independent. (We cannot quite say that the elements of E are the
columns and independence is linear independence, since E might have repeated
columns: this is exactly the problem that led us to put the matroid structure on
the set {1, . . . , n} rather than on the set of columns.) More precisely, the function
χ mapping i to the ith column is a representation of M over F. How do the
elementary operations affect the matroid representation?
We see that row operations on A don’t change M but replace the representation
χ by an equivalent representation. (Two representations are called equivalent if
they differ by an invertible linear transformation of the embedding vector space.)
On the other hand, column permutations and scalar multiplications replace M
by an isomorphic matroid; effectively, permutations re-label the elements, while
scalar multiplications have no effect at all.
So let’s call two matrices A and A0 CM-equivalent if A0 is obtained from A
by an arbitrary row operation and a permutation of the columns together with

67
multiplication of individual columns by non-zero scalars. Now we see that CM-
equivalence classes of matrices correspond bijectively to both monomial equiv-
alence classes of linear codes, and equivalence classes of representations of ma-
troids, under the natural notions of equivalence in each case.
Thus we expect information to transfer back and forth between code and ma-
troid.
It is possible to go directly from the vector matroid to the code, without the
intervening matrix, as follows.
Let v1 , . . . , vn be vectors spanning the vector space V . The corresponding code
is
{(v1 f , . . . , vn f ) : f ∈ V ∗ },
where V ∗ is the dual space of V , and v f is the image of v under f . THis is because
the function giving the ith coordinate of a vector is an element of the dual space,
and these functions form a basis for the dual space.
I leave as an exercise the problem of finding a matrix-free construction of the
matroid from the code.
Now we have the following important observation:

Proposition 7.1 If the matroid M corresponds to the code C, then the dual ma-
troid M ∗ corresponds to the dual code C⊥ .

Proof If the matrix A happens to be in the form [Ik B], where Ik is a k × k iden-
tity matrix and B is k × n − k, then both the dual code and the dual matroid are
represented by the matrix [−B> In−k ].
In general, we can choose k linearly independent columns, move them to the
front by a permutation, apply the above argument, and then apply the inverse
permutation.

Example Let us work out the matroid corresponding to the dual of the extended
Hamming code that we met in Chapter 1. This is the code whose generator matrix
is the binary matrix
 
0 0 0 1 1 1 1
A = 0 1 1 0 0 1 1.
1 0 1 0 1 0 1

The vectors representing the matroid are the columns of the matrix. We see
that any two columns are linearly independent, while the sets of three columns

68
which are linearly dependent are precisely the lines of the Fano plane, the Steiner
system S(2, 3, 7):
u001
T
'$
u011 Tu101
 T
b
 b" bu""
111T
" " b
bT
 &%
u
" u bTu
010 110 100

7.2 Graphic matroids

Theorem 7.2 A graphic matroid is representable over any field.

Proof Let X be a graph with n vertices v1 , . . . , vn , amd m edges e1 , . . . , em . We

construct the so-called signed incidence matrix A of X as follows: A is an n × m
matrix with rows indexed by vertices and columns by edges. If the edge ei is a
loop, then the ith column of A is zero. Otherwise, if ei joins vertices v j and vk ,
with j < k, then we take the ith column to have jth entry 1, kth entry −1, and all
other entries 0.
We claim that the columns of A give a matrix representation of M(X).
• If e is a loop, the corresponding vector is zero.
• Similarly, if e1 and e2 join the same two vertices, the corresponding columns
are equal, and so are linearly dependent.
• Suppose that there is a cycle (v1 , v2 , . . . , vr ) contained in a set A of edges.
If ei = {vi , vi+1 } for i = 1, . . . , r − 1 and er = {vr , v1 }, then take the sum of
the columns corresponding to these edges, with sign +1 if vi < vi+1 and −1
otherwise. The entry corresponding to a vertex vi comes from two edge, and
the contributions have opposite signs and so cancel out. So the sum of the
columns is zero, and they are linearly dependent. In a similar way, if a set of
edges is acyclic, then the corresponding columns are linearly independent.
So we have indeed represented the matroid M(G), whose independent sets
are the sets of edges containing no cycles.

Note that, if the field has characteristic 2, then + and − are the same, and so
the signs can be ignored: the sum of columns corresponding to edges in a cycle
involves each vertex of the cycle twice, and so is zero.
Not every matroid is representable. Moreover, a matroid may be representable
over some fields but not others. See the last section of the notes.

69
7.3 Greene’s Theorem
The following theorem was proved by Curtis Greene.

Theorem 7.3 Let C be a code over a field with q elements, and M the correspond-
ing vector matroid. Then
 
n−dim(C) dim(C) X + (q − 1)Y X
WC (X,Y ) = Y (X −Y ) TM , .
X −Y Y

Note that, if x = (X + (q − 1)Y )/(X −Y ) and y = X/Y , then

(x − 1)(y − 1) = q.

So the weight enumerator is an evaluation of the Tutte polynomial along a partic-

ular hyperbola in the “Tutte plane”.

Proof The proof is by induction. For M, we have the “deletion-contraction rule”

proved in the last section.
The analogues of deletion and contraction of a matroid are the operations of
puncturing and shortening a code, defined as follows.
To puncture a code at the ith position, we simply delete the ith coordinate
from all codewords. To shorten it at the ith position, we take the subcode consist-
ing of all codewords with zero in the ith position, and then delete this position.
We denote by C0 and C00 the codes obtained by puncturing and shortening C in a
specified position. It is easy to see that puncturing and shortening correspond to
deletion and contraction of the corresponding element of the matroid.
A loop in the M corresponds to a coordinate where all codewords have the
entry 0. A coloop is a bit more complicated, but can be described as a coordinate
such that (after row operations) the first entry in that column of the generator
matrix is 1, while all other entries in that column or in the first row are 0.
If the element i of the matroid corresponds to the distinguished coordinate, we
have the following recursive scheme for the weight enumerator:

(a) If C has length 0, then WC (X,Y ) = 1.

(b) If i is a loop, then WC (X,Y ) = XWC0 (X,Y ).

(c) If i is a coloop, then WC (X,Y ) = (X + (q − 1)Y )WC00 (X,Y ).

70
 (d) If i is neither a loop or a coloop, then

WC (X,Y ) = YWC0 (X,Y ) + (X −Y )WC00 (X,Y ).

Part (a) is obvious; part (b) holds because each word in C has one extra zero
than the corresponding word in C0 . Part (c) holds because each word w in C00 gives
rise to q words in C (all possible entries occur in the added coordinate), of which
one has the same weight as w and q − 1 have weight one greater.
Said otherwise, we may suppose that i = 1. if i is a loop, then C = {0} ⊕ C0 ,
where {0} is the code of length 1 containing only the zero word. If i is a coloop,
then C = F ⊕C00 , where F is the one-dimensional code of length 1 in which every
element of F occurs. Now use the facts that

• if C = C1 ⊕C2 , then WC = WC1 ·WC2 ;

• if C = {0}, then WC = X;
• if C = F, then WC = X + (q − 1)Y , since C contains zero and q − 1 non-zero
elements.

Finally, suppose that e is neither a loop nor a coloop. Let W1 and W2 be the
sums of terms in WC corresponding to words with zero, resp. non-zero, entry in
position e. Then WC = W1 + W2 . We also have WC0 = W1 /X + W2 /Y , and WC00 =
W1 /X. The assertion follows.
Now induction, together with the deletion-contraction rule for the Tutte poly-
nomial, proves the theorem. (In the proof below, x = (X + (q − 1)Y )/(X −Y ) and
y = X/Y .)

• If C has length 0, then WC = 1 and TM = 1.

• If i is a loop, then
Y
WC = XWC0 = X(Y n−1−dim(C) (X −Y )dim(C) TM () = Y n−dim(C) (X −Y )dim(C) TM .
X

• If i is a coloop, then
X −Y
WC = (X +(q−1)Y )WC00 = (X = (q−1)Y )(Y n−dim(C) (X −Y )dim(C)−1 TM () = Y n−dim(C)
X − (q − 1)Y

71
 • Finally, if i is neither a loop nor a coloop, then

WC0 = Y n−1−dim(C) (X −Y )dim(C) TM\i ,

WC00 = Y n−dim(C) (X −Y )dim(C)−1 TM/i ,
TM = TM\i + TM/i ,

so we have
WC = YWC0 + (X −Y )WC00 .

From Greene’s theorem and the earlier observation, we can deduce MacWilliams’
Theorem, which shows that the weight enumerator of the dual code C⊥ can be cal-
culated from that of C.
Theorem 7.4
1
WC⊥ (X,Y ) = WC (X + (q − 1)Y, X −Y ).
|C|

Proof Since C⊥ has dimension n − dim(C) and corresponds to the dual matroid
M ∗ , we have
 
dim(C) n−dim(C) X X + (q − 1)Y
WC⊥ (X,Y ) = Y (X −Y ) TM , .
Y X −Y

On the other hand, we have

1
WC (X + (q − 1)Y, X −Y )
|C|
 
− dim(C) n−dim(C) dim(C) qX X + (q − 1)Y
=q (X −Y ) (qY ) TM , .
qY X −Y

The two expressions are equal.

Note that this proof is entirely combinatorial, in contrast to the algebraic proof
given in the first chapter.

72
7.4 Matroids and Steiner systems
Recall that a Steiner system S(t, k, n) consists of a set of n points with a collection
of k-element subsets of the point set called blocks, such that any t points are
contained in exactly k blocks.
Just as the Fano plane gave us a rank 3 matroid, so a Steiner system gives
rise to a rank t + 1 matroid: the independent sets are all the sets of points with
cardinality at most t, together with all sets of t + 1 points which are not contained
in a block.
I leave as an exercise the proof that this construction does give a matroid.
Here is the proof that the Fano matroid is representable over a field F if and
only if the characteristic of F is 2. We have seen that it is representable over the
field with two elements, and this is a subfield of every field of characteristic 2; so
we have the result one way round.
Suppose that the points are numbered as shown.
1 u
T
'$
u u
 T
3
b u" "T 5
 b"b7 T
"" bbT
 &%
u
" u bTu
2 6 4
Suppose we have a representation over F. Since the matroid has rank 3, the
points are mapped to elements of F3 . Since {1, 2, 4} is a basis, we can assume that
its points are mapped to (0, 0, 1), (0, 1, 0), and (1, 0, 0) respectively.
The point 6 is a linear combination of 2 and 4, but not a multiple of either; so
the coefficients are both non-zero, and we can divide by one of them to assume
that 6 maps to (1, x, 0). Similarly, 3 maps to (0, 1, y), and 5 to (z, 0, 1). Now
using the three lines through 7, we find three expressions for its coordinates (up to
scalar multiples), say (1, x, a), (b, 1, y) and (z, c, 1). Thus for example b(1, x, a) =
(b, 1, y), so bx = 1 and ba = y, with four further equations from the other pairs.
From these equations we deduce that xyz = 1.
Now, instead, consider the line 356, which shows that these three points are
linearly dependent. So

1 x 0
0= 0 1 y = 1 + xyz,
z 0 1

so xyz = −1.

73
 We conclude that +1 = −1, so that F has characteristic 2.
Those with a good background in Euclidean geometry may recognise the the-
orems of Ceva and Menelaus here!

Exercises
7.1. Show that the matroid associated to a linear code is uniform if and only if
the code is MDS. (See Exercise 4 of Chapter 1.)
7.2. Calculate the weight enumerator of the code associated with a representation
of U3,n over GF(q). Find examples with n = q + 1.
7.3. Describe the matroid corresponding to the [7, 4, 3] binary Hamming code.
7.4. Prove that the construction in the last section does give a matroid.

74
8 Cycle index
Counting things “up to symmetry” means counting the orbits of some group of
symmetries on the set of things in question. Such a problem can always be solved
by using the orbit-counting lemma, which we met in Chapter 4. But often the
counting can be systematised by the use of a multivariate polynomial associated
with a permutation group, called the cycle index.

8.1 The definition

We have a set of size n on which our permutations will act, say Ω = {1, 2, . . . , n}.
Any permutation g of Ω can be decomposed as a product of disjoint cycles in a
unique way, up to changing the order in which the cycles are written and changing
the starting point of each cycle. For example,

(1, 2, 3)(4, 5) = (4, 5)(1, 2, 3) = (2, 3, 1)(5, 4).

We describe the cycle lengths of a permutation g by a monomial z(g) in indeter-

minates s1 , s2 , . . . , sn as follows:
c (g) c2 (g) c (g)
z(g) = s11 s2 · · · snn .

where ci (g) is the number of cycles of length i in G.

Now we define the cycle index of a permutation group G by
1
Z(G) = ∑ z(g).
|G| g∈G

So Z(G) is a polynomial in s1 , . . . , sn .

Example In Chapter 4, we considered the group G of rotations of a cube, acting

as a permutation group on the set of six faces of the cube. To recap briefly:
The group G has order 24. Its elements are of the following type:

• The identity, which fixes all six faces.

• A rotation through a half-turn about a face-axis fixes the two faces on the
axis and has two cycles of length 2 on the remaining faces. There are three
such elements.

75
 • A rotation through a quarter turn about a face-axis fixes the two faces on
the axis and has a single 4-cycle on the remaining faces. There are six such
elements.
• A half-turn about an edge-axis fixes no faces, permuting them in three 2-
cycles. There are six such rotations.
• A third-turn about a vertex-axis joining opposite vertices permutes the faces
in two 3-cycles. There are eight such rotations.

So the cycle index of this group is

1 6
Z(G) = (s + 3s21 s22 + 6s21 s4 + 6s32 + 8s23 ).
24 1
You might observe that, if you set all the variables equal to 3, the cycle index
evaluates to 57, which is the number of orbits of G acting on colourings of the
faces with three colours. But this is only a small part of what the polynomial can
do. In the next section, we probe a little deeper.

8.2 The Cycle Index Theorem

We are going to allow ourselves the possibility of decorating the faces of the cube
with something more elaborate than just three colours.
Let F be a set of figures. Each figure has a non-negative integer weight.
The number of figures may be infinite, but we require that there are only a finite
number of figures of any given weight i. The figure-counting series is the formal
power series
A(x) = ∑ ai xi ,
i≥0

where ai is the number of figures of weight i. In most of our applications, the set
of figures is finite, and A(x) is a polynomial.
A function, or configuration, on a finite set Ω is a function from Ω to F . We
can think of a function φ as attaching a figure φ (x) to each element x ∈ Ω. Any
function φ has a weight, obtained by summing the weights of the figures φ (x) as
x runs through Ω. The number of functions of given weight is clearly finite.
Now let G be a permutation group on Ω. Then G permutes the set of functions,
by the rule
(φ .g)(x) = φ (x.g−1 ).

76
(The inverse here is just to satisfy the rule for an action, namely that (φ .g).h =
φ .gh, rather than φ .hg. This makes no difference to the orbits or the counting
problem that we are going to solve.) The function-counting series associated with
the triple (G, Ω, F ) is
B(x) = ∑ bi xi ,
i≥0

where bi is the number of orbits of G on the set of functions of weight i.

Theorem 8.1 (Cycle Index Theorem) B(x) is obtained from the cycle index Z(G)
by substituting a(x j ) for s j , for j = 1, 2, . . . , n = |Ω|.

Before proving this theorem, we will give a couple of examples of its applica-
tion.

Example: The cube We can re-solve the question about the 3-coloured cube
using the Cycle Index Theorem. We take the figures to be the three colours, each
of weight 0. Then the figure-counting series is 3, and the function-counting series
is obtained by substituting 3 for each si , as claimed.
But we can refine the count. In how many ways can we colour the faces of the
cube with three colours, red, green and blue, with a given number of red faces?
We can take “red” to be a figure of weight 1, and “green” and “blue” each to have
weight 0, giving the figure-counting series x + 2. So, if we substitute x j + 2 for s j
for each j, we obtain a polynomial in x, where the coefficient of xi is the number
of colourings having i red faces. This polynomial turns out to be

x6 + 2x5 + 6x4 + 10x3 + 12x2 + 16x + 10.

As a small reality check, there is only one colouring with all six faces red, and
two with five red faces (the sixth face can be green or blue, but it doesn’t matter
where it is); the six colourings with four red faces represent the combinations of
three choices of colour (green-green, green-blue and blue-blue) with two choices
of position (adjacent or opposite) for the non-red faces.
If we want to count colourings with given numbers of faces of each colour, we
can use three indeterminates r, g and b, and substitute r j + g j + b j for s j for each
j. This appears to require a slight extension of the Cycle Index Theorem, but in
fact can be proved from the theorem as stated by choosing weights suitably.

77
Example: Unlabelled graphs The number of simple graphs (no loops or multi-
ple or directed edges) on a set of n vertices is 2n(n−1)/2 , since a graph is determined
by the subset of all possible pairs which are edges. 
Similarly, the number of graphs
n(n − 1)/2
on a given vertex set with m edges is .
m
What if we want to count graphs “up to isomorphism”? (This is usually re-
ferred to as counting unlabelled graphs, since we are effectively removing the
vertex labels.)
An isomorphism class of graphs is an orbit of the symmetric group Sn on
sets of edges. So our first job is to calculate the cycle index of the permutation
{2}
group (usually referred to as Sn ) induced by Sn on the set of 2-element subsets
of {1, . . . , n}. This can be done by taking each cycle type for Sn , and calculating
the cycle lengths for its action on the set of pairs.
Then we take two figures, an edge (weight 1) and a non-edge (weight 0).
The function-counting series is a polynomial in which the coefficient of xm is the
number of graphs with n vertices and m edges up to isomorphism.
There is a formula for the general case, somewhat complicated. Here is how
it works for n = 4. The elements of S4 are as follows:
• the identity, with four 1-cycles on points, 6 1-cycles on pairs;
• six transpositions, each fixing two pairs and having two 2-cycles;
• three double transpositions, with the same cycle structure on pairs;
• eight 3-cycles, each with two 3-cycles on pairs;
• six 4-cyles, each with a 2-cycle and a 4-cycle on pairs.
So
{2} 1 6
Z(S4 ) = (s + 9s21 s22 + 8s23 + 6s2 s4 ),
24 1
and the polynomial enumerating unlabelled graphs on four vertices is
x6 + x5 + 2x4 + 3x3 + 2x2 + x + 1,
or 11 graphs altogether.
In this small case, we could simply list all the graphs; but knowing the numbers
provides a valuable check on the list!
In this example and the previous one, we have a group which is abstractly
isomorphic to S4 , acting on a set of 6 points (faces of a cube, or 2-element subsets
of {1, . . . , 4}); but the cycle indices are different. Indeed, the actions themselves
are different. The point stabiliser in the first case is the cyclic group C4 ; in the
second case it is C2 ×C2 .

78
8.3 Sketch proof of the Cycle Index Theorem
Our data consists of a permutation group G acting on a set Ω, with cycle index
Z(G), and a set F of figures, with figure-counting series A(x). We have to show
that the number of orbits of G on functions of weight i is the coefficient of xi in
the polynomial obtained by substituting A(x j ) for s j in Z(G).
First, we want to count the functions of weight i. We claim that the number
of functions is the coefficient of xi in A(x)n . For suppose we have a function φ
for which the weight of φ ( j) is w j ; the numbers w1 , . . . , wn sum to i. Now there
are awi choices of a figure of weight w1 for φ (1), aw2 choices for φ (2), and so
on. Multiplying these together, and summing over all choices of w1 , w2 , . . . which
sum to i, we obtain the coefficient of xi in A(x)n , as required.
Note that this is the special case of the Cycle Index Theorem when G is the
trivial group (with cycle index sn1 ).
Now we are going to use the Orbit-counting Lemma to count the orbits of G on
these functions, so we need to find out how many functions of weight i are fixed
by an element g ∈ G. I claim that this is the coefficient of xi in the polynomial
obtained from z(g) by substituting A(x j ) for s j , for j = 1, . . . , n.
To see this, we observe that a function is fixed by g if and only if it is constant
over the cycles of g. For each cycle Ck , of length lk , then, we get to make a choice
of figure (of weight wk , say); the contribution of the cycle to the weight of the
function is lk wk , so the number of choices is the coefficient of xlk wk in A(xlk ). By
the same argument as before, we see that the number of fixed functions is the
coefficient of xi in A(xl1 )A(xl2 ) · · ·; and this polynomial is exactly what we obtain
from z(g) by the stated substitution.
Finally, apply the Orbit-counting Lemma. The operation of averaging poly-
nomials over elements of G commutes with substitution and extracting the coeffi-
cient of xi , so the required number of orbits is the coefficient of xi in
1
∑ z(g) = Z(G)
|G| g∈G

with the stated substitution.

8.4 Permutation character

The permutation character of a permutation group G is the function π : G → N
given by π(g) = fix(g), the number of fixed points of G.

79
 The permutation character is an example of the general notion of a character
of a group, which we will not need. The question is: the cycle index of a permu-
tation group tells us about cycles of every length, not just cycles of length 1. Can
we compute the cycle index from the permutation character?
The answer is: almost. The extra information we need is the collection of
power maps on G, in other words, if g is an element of order l, and k divides l, we
need to know which element is gk . (Actually, much less is required; we only need
to know which conjugacy class contains gk .)
For let g have order l, and have ci cycles of length i for each i dividing l. Then
the number dk of fixed points of gk is the number of points lying in cycles of g
whose length divides k, that is,

dk = ∑ ici .
i|k

These are a system of linear equations for the ci in terms of the dk , with lower
triangular matrix, so there is a unique solution. Indeed, classical Möbius inversion
from number theory shows that

kck = ∑ di µ(k/i),
i|k

where µ is the Möbius function, defined by

(−1)r if n is the product of r distinct primes,


µ(n) = .
0 if n has a repeated prime factor.

For example, suppose that g is an element of order 12, where the numbers of
fixed points of g, g2 , g3 , g4 , g6 , g12 are respectively 1, 3, 4, 7, 12, 28. Without
using the Möbius function, we have

c1 = 1
c1 + 2c2 = 3 so c2 = 1
c1 + 3c3 = 4 so c3 = 1
c1 + 2c2 + 4c4 = 7 so c4 = 1
c1 + 2c2 + 3c3 + 6c6 = 12 so c6 = 1
c1 + 2c2 + 3c3 + 4c4 + 6c6 + 12c12 = 28 so c12 = 1.

So z(g) = s! s2 s3 s4 s6 s12 .

80
 Using Möbius inversion finds the values directly: no need to solve iteratively
or use earlier results. For example,

12c12 = 28 − 12 − 7 + 3 = 12,

so c12 = 1. Exercise: Calculate the other ci this way.

As a consequence of this analysis, we see that two permutation actions of the
same group with the same permutation character have the same cycle index.

8.5 Factorisation
For the Tutte polynomial, we understand its factorisations, thanks to a remarkable
theorem of Merino, de Mier and Noy. The direct sum M1 ⊕ M2 of two matroids
M1 = (E1 , I1 ) and M2 = (E2 , I2 ) is the matroid on the disjoint union of E1 and
E2 , whose independent sets are all unions of a set in I1 and a set in I2 . It is
straightforward to show that

TM1 ⊕M2 (x, y) = TM1 (x, y)TM2 (x, y).

The theorem referred to states that the converse is also true. Call a matroid inde-
composable if it is not isomorphic to the direct sum of two non-empty matroids.

Theorem 8.2 If M is indecomposable, then its Tutte polynomial is irreducible in

Z[x, y], and even in C[x, y].

Does a similar theorem hold for cycle index?

The answer is no in general. The analogue of the easy direction still works.

Proposition 8.3 Let G be the direct product of two permutation groups G1 and
G2 , acting on disjoint sets Ω1 and Ω2 . Regarding G as a permutation group on
Ω1 ∪ Ω2 , we have
Z(G1 × G2 ) = Z(G1 )Z(G2 ).

But there are some “accidental” factorisations of the cycle index. For example,
let G = C3 × C3 in its regular action on 9 points. Then G is transitive, and every
element except the identity has three 3-cycles; so
1 1
Z(G) = (s91 + 8s33 ) = (s31 + 2s3 )(s61 − 2s31 s3 + s23 ).
9 9

81
(Note that the first factor is the cycle index of the group C3 .) Various other exam-
ples occur as well, and not much is known.
A permutation group G on Ω is primitive if it fixes no partition of Ω apart
from the trivial partitions (the partition into singletons and the partition with just
one part). We have learned much about primitive groups since the Classification
of Finite Simple Groups. But the following is still open:

Conjecture If G is primitive, then Z(G) is irreducible.

Exercises
8.1. Consider the cyclic group of order 5 acting on a set of 20 points, with four
orbits of length 5. Write down and factorise the cycle index of this permutation
group.
8.2. Prove, using the cycle index theorem, the claim in the text that the polyno-
mial enumerating face colourings of the cube with three colours up to rotational
symmetry is obtained by substituting ri + gi + bi for si in Z(G), where G is the
rotation group of the cube. [Hint: Let red, green and blue have weights 0, 1 and w
respectively.]
8.3. Show that

• substituting si = 1 for all i in Z(G) gives the answer 1;

• substituting s1 = 1 and si = 0 for i > 1 gives the answer 1/|G|;
• differentiating with respect to s1 and then substituting si = 1 for all i gives
the number of orbits of G.

8.4. In how many ways can we colour the faces of the regular octahedron red, blue
and green (up to rotational symmetry) so that there are i red faces, for 0 ≤ i ≤ 8?
8.5. Re-do Exercise 4.1 from chapter 4 using the cycle index theorem.

82
9 IBIS groups
In this section we will look at a somewhat unexpected connection between groups
and matroids. We will focus on bases for these structures.
A basis for a vector space has two features:

• there is a convenient way of expressing any vector uniquely in terms of the

basis (as a linear combination of basis vectors);

• all bases contain the same number of elements, and indeed bases have the
exchange property (that is, if B1 and B2 are bases and x is an element of B1
which is not in B2 , then there is an element y in B2 but not in B1 so that,
when x is replaced by y, a basis is obtained.

We saw that matroid bases have the second property, but not the first: there is
no general way of writing matroid elements in terms of a basis.
We are going to consider bases for permutation groups, which in general will
have a version of the first property but not the second. However, for a particular
class of groups (the IBIS groups of the title), both properties will hold.

9.1 Bases
Let G be a permutation group on a finite set Ω. where |Ω| = n.
A sequence (x1 , x2 , . . . , xr ) of points of Ω is called a base for G if the only
element of G which fixes all points in the sequence is the identity. Normally our
goal is to find a relatively small base for G if we can.

Examples

• Let G be the symmetric group Sn . Then any sequence containing n − 1 or n

distinct points is a base. (If all but one points are fixed, the last point must
also be fixed.)
• Let G be the alternating group An . Then a sequence of n − 2 distinct points
is a base. For there are just two permutations in Sn which fix n − 2 points;
one of them is a transposition of the remaining two points, so does not lie
in An .
• Let G be the general linear group (the group of all invertible linear maps)
on a d-dimensional vector space V over a finite field. Then a set is a base

83
 for G if and only if it contains a basis for the vector space; so the smallest
base has size d.
Bases for a permutation group resemble bases for a vector space in one respect.
In a vector space, every vector can be uniquely expressed in terms of the vectors
of a basis (as a linear combination). Nothing like this is true for arbitrary matroids,
say. However, for permutation groups, we have:

Proposition 9.1 Let (x1 , x2 , . . . , xr ) be a base for G. Then any element g ∈ G is

uniquely determined by (x1 g, x2 g, . . . , xr g).

Proof Suppose that h is another element for which xi h = xi g for i = 1, . . . , r. Then

xi (gh−1 ) = xi for i = 1, . . . , r. By the definition of a base, gh−1 = 1, and so g = h,
contrary to assumption.

The consequence of this is that, if we are doing calculations in a permutation

group, we don’t have to remember the permutation g completely; it is enough to
remember its values on the points of a base. This can lead to big savings of space
in computation with permutation groups. It also motivates us to look for small
bases.
Finding the smallest base for a permutation group is in general a hard problem.
But we can get an upper bound by the following algorithm.
Start with H = G, and b = () (the empty sequence).
While H 6= {1}, choose a point x not fixed by H; add x to the
sequence b, and replace H by the stabiliser of x (the subgroup of
H consisting of permutations fixing x).
Return b.
A base produced by this algorithm is irredundant: that is, no base point is
fixed by the stabiliser of the earlier points in the sequence.

Example The automorphism group of the Petersen graph has irredundant bases
of sizes 3 and 4. For recall that we can identify the vertices of the graph with the 2-
element subsets of {1, 2, 3, 4, 5}; two vertices are joined whenever the correspond-
ing subsets are disjoint, and the automorphism group of the graph is isomorphic
to S5 . Now
• the sequence ({1, 2}, {3, 4}, {1, 3}) is an irredundant base of size 3;

84
 • the sequence ({1, 2}, {3, 4}, {1, 5}, {3, 5}) is an irredundant base of size 4.
So, unlike bases in a vector space (or indeed a matroid), irredundant bases for
permutation groups need not all have the same size.
Note also that, in the second case, if we re-order the base as ({1, 2}, {3, 5}, {1, 3}, {3, 4}),
then it is no longer irredundant, since the stabiliser of the first three points is al-
ready the identity.

9.2 IBIS groups

However, there is a special class of permutation groups for which all the irredun-
dant bases have the same size.

Theorem 9.2 For a permutation group G, the following conditions are equiva-
lent:
(a) any two irredundant bases have the same size;
(b) any re-ordering of an irredundant base is an irredundant base;
(c) the irredundant bases are the bases of a matroid on Ω.

A permutation group which has these equivalent properties is called an IBIS

group. The name is an acronym for “Irredundant Bases of Invariant Size”.

Proof The proof that (c) implies (a) is immediate, since matroids have the prop-
erty that all their bases have the same size (a consequence of the Exchange Prop-
erty).
Let us prove that (a) implies (b). Note that if we have any base for a permuta-
tion group, we can produce an irredundant base simply by dropping “resdundant”

85
elements (points fixed by the stabiliser of their predecessors). Suppose, then, that
(x1 , . . . , xr ) is an irredundant base, but that some ordering of it fails to be irredun-
dant. Then we can get an irredundant base by dropping some elements. But then
we have produced irredundant bases of different sizes, which is not possible if we
assume (a).
Finally we show that (b) implies (c). Recall that the bases of a matroid are
characterised by the Exchange Property: if B1 and B2 are bases and x ∈ B1 \ B2 ,
then there exists y ∈ B2 \ B1 such that B1 \ {x} ∪ {y} is a basis. We show that, if
(b) holds, then the irredundant bases of a permutation group satisfy this axiom.
So let B1 and B2 be irredundant bases, and let x ∈ B1 \ B2 .
Let b be the following sequence: write all the elements of B1 except for x,
then all the elements of B2 . This is a base (since it contains the base B2 ), and so
we can produce an irredundant base by deleting redundant elements. None of the
elements of B1 \ {x} get deleted in this process, since this is part of an irredundant
base. If we only use one element y ∈ B2 , we have the required element, and we
are done. So suppose instead that this process requires at least two elements of
B2 , say y1 , . . . , yl .
Now the sequence formed by the elements of B1 \ {x}, then y1 , . . . , yl−1 , then
x, is a base (since it contains B1 ), and is clearly irredundant. But the sequence
formed by the elements of B1 \ {x}, then x, then y1 , . . . , yl−1 is not an irredundant
base, since by the time we get to x the stabiliser is already the identity and no more
elements are required. Thus (b) is contradicted.
The proof is done.

9.3 Examples
The symmetric group Sn is an IBIS group: any sequence of n − 1 distinct points is
an irredundant base, so the matroid is the uniform matroid Un,n−1 .
The alternating group An is similarly an IBIS group, with matroid Un,n−2 . The
general linear group GL(d, q) is an IBIS group, whose matroid is the vector ma-
troid formed by all the vectors in the d-dimensional vector space.
The cyclic group Cn , in its usual action on n points, is an IBIS group with
matroid Un,1 . The dihedral group D2n (the symmetry group of a regular n-gon)
is a little more interesting. If n is odd, then any two points form a base, so the
matroid is Un,2 . But if n is even, the irredundant bases are the pairs of points
which are not opposite in the n-gon. So the matroid is obtained from Un/2,2 by
“blowing up” any element in to a dependent pair of elements.

86
 There are some interesting examples among the sporadic groups. The Math-
ieu group M12 , the automorphism group of the Steiner system S(5, 6, 12), is 5-
transitive, and the stabiliser of any five points is the identity. So it is an IBIS
group of rank 5, with matroid U12,5 . (Note that this is not the same as the matroid
we derived from the Steiner system).
A much more interesting case is the Mathieu group M24 , the automorphism
group of the Steiner system S(5, 8, 24). This group is also 5-transitive, so any
five points can be the first five points of an irredundant base. The stabiliser of five
points fixes the block containing them, and has two orbits of sizes 3 (the remaining
points of the block) and 16 (the points outside the block). Adding one point from
each orbit gives a base; also, any two points from the orbit of length 16 form a
base. So any irredundant base has size 7, and the group is an IBIS group with a
matroid of rank 7. But not very much is known about this matroid. For example,
we don’t know if it is representable in a vector space.
A very interesting problem is to determine all IBIS groups, or (a more modest
goal) all matroids which arise from IBIS groups. Very little is known about this,
except a result which describes all the groups in the case where the matroid is
uniform.
The examples in the next section show that this problem may be more difficult
than it first appears.

9.4 Codes and matroids revisited

Let C be a linear [n, k] code over GF(q), that is, a k-dimensional subspace of
GF(q)n . We have seen that there is a matroid associated with the code C, repre-
sented by the columns of a generator matrix for C; it is a representable matroid
(the columns are n vectors in GF(q)k ), and we saw Greene’s theorem, giving a
connection between the Tutte polynomial of the matroid and the weight enumera-
tor of the code.
In this section, we construct from C a permutation group G, which turns out
to be an IBIS group. This gives a matroid, which has a Tutte polynomial; and also
the group has a cycle index. We will link up various polynomials as shown in the
diagram.

87
   
Tutte polynomial Tutte polynomial
→
of M(C) of M(G)
  
↓
  
Weight enumerator Cycle index
→
of C of G
  
The down arrow is Curtis Greene’s theorem; we will see below how the two
right arrows work (Propositions 9.3, 9.4).
We take Ω (the set of points on which the group acts) to be the Cartesian
product {1, 2, . . . , n} × GF(q). The group G will be the additive group of C. A
codeword c = (c1 , c2 , . . . , cn ) acts on Ω by the rule
(c1 , c2 , . . . , cn ) : (i, x) 7→ (i, x + ci ),
for i ∈ {1, . . . , n}, x ∈ GF(q).
Now, assuming that there are codewords of C which are non-zero in the ith
position for all i (we can simply delete any coordinates not satisfying this), we
see that for each i, the set Ωi = {(i, x) : x ∈ GF(q)} is an orbit of G. For C is a
subspace, so if there is any codeword whose ith coordinate is non-zero, then every
element of GF(q) will appear in the ith coordinate of some codeword.
When we stabilise one point of Ωi , we fix them all. So an irredundant base
will contain at most one point from each such set. Moreover, it is easy to see
that an irredundant base must include points from the sets (Ωi : i ∈ B), where the
columns in B form a basis for the matroid. So G is an IBIS group of rank k; the
bases of the IBIS matroid are all k-tuples ((i1 , x1 ), . . . , (ik , xk )), where {i1 , . . . , ik }
is a basis for the matroid associated with the code and x1 , . . . , xk are arbitrary field
elements. So the IBIS matroid is the code matroid with each point “blown up” to
a set of size q of pairwise dependent points.
How does this affect the Tutte polynomial?
Define the q-fold inflation 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.
Proposition 9.3 If M(q) is a q-fold inflation of M, then
 q
y − 1 ρ(E) xy − x − y + yq q
  
TM(q) (x, y) = TM ,y .
y−1 yq − 1

88
Proof To each subset A ⊆ E × Q, we can define a projection map π to a subset
B of E, where B consists of all the first coordinates of sets in A. Fo any B ⊆ E,
there are (2q − 1)|B| subsets of E × Q whose projection onto E is B. For any such
subset A, the rank (in Mq ) is equal to the rank of B in M. The contribution to the
Tutte polynomial from such sets is given by
!
|B| q  
ρ(E)−ρ(B) |B|−ρ(B) q j−1
(x − 1) (y − 1) ∏ ∑ j (y − 1)
i=1 j=1

= (x − 1)ρ(E)−ρ(B) (y − 1)|B|−ρ(A) (yq − 1)|B|

 q ρ(B)
ρ(E)−ρ(A) y − 1
= (x − 1) (yq − 1)|B|−ρ(B)
y−1
 q
y − 1 ρ(E) (x − 1)(y − 1) ρ(E)−ρ(B) q
  
= (y − 1)|B|−ρB .
y−1 yq − 1

Summing over A ⊆ E, we obtain

yq − 1
 ρ(E)  ρ(E)−ρ(B)
(x − 1)(y − 1)
TM(q) (x, y) = ∑ (yq − 1)|B|−ρ(B)
y−1 B⊆E yq − 1
yq − 1 ρ(E)
   
(x − 1)(y − 1) q
= TM + 1, y .
y−1 yq − 1

We can also relate the cycle index of the IBIS group to the Tutte polynomial
of the matroid in this case.

Proposition 9.4 Let WC (X,Y ) be the weight enumerator of a code C over GF(q),
where q = pe . Then the cycle index of the IBIS group defined above from C is
1 q q/p
Z(G) = WC (s1 , s p ).
|C|

Proof Let c be a codeword, having weight d, and also let c denote the corre-
sponding permutation in G. Then c contributes X n−d Y d to the weight enumerator.
Also, c fixes all the points (i, x) for which ci = 0 (there are q(n − d) of these) and
permutes the remaining qd points in qd/p cycles of length p, since px = 0 for
every x ∈ GF(q). The result follows.

89
9.5 Greedy bases
It is computationally hard to find the minimum base size for a permutation group.
We have seen that it is easy to find an irredundant base. This might be bigger than
the minimum, but cannot be too much bigger:

Theorem 9.5 Let G be a permutation group on n points, whose minimum base

size is r. Then any irredundant base for G has size at most r log2 n.

Proof We show that, if G has an irredundant base of size s, then

2s ≤ |G| ≤ ns .

For let Hi be the stabiliser of the first s base points for 0 ≤ i ≤ s. Then H0 = G and
Hs = {1}. Also, the index of Hi in Hi−1 is equal to the size of the orbit of Hi−1
containing the ith base point, which is at least 2 (since the base is irredundant) and
at most n (since there are only n points). Finally,
s
|G| = |H0 : Hs | = ∏ |Hi−1 : Hi |,
i=1

and the inequality follows.

So, if r is the minimum base size and s is the size of any irredundant base, then
we have
2s ≤ |G| ≤ nr ,
so s ≤ r log2 n, as required.

We saw that, for computational purposes, it is often useful to find a small base
for a permutation group. There is a “greedy algorithm” which gives a fairly good
heuristic for this.
Suppose that b = (x1 , x2 , . . . , xr ) is a base for G, and let Hi be the subgroup
of G stabilising the first i base points (so that H0 = G and Hr = {1}). Now the
index of Hi in Hi−1 is equal to the size of the orbit of Hi−1 containing xi (by the
Orbit-Stabiliser Theorem), and the product of these indices over all i is |G|. So,
heuristically, to find a small base, we should make each index as large as possible:
that is, modify the algorithm for choosing an irredundant base as follows:

Start with H = G, and b = () (the empty sequence).

90
 While H 6= {1}, choose a point x in an orbit of H of maximum
size; add x to the sequence b, and replace H by the stabiliser of
x (the subgroup of H consisting of permutations fixing x).
Return b.

This is the greedy algorithm.

The greedy algorithm doesn’t always find a smallest base. But the following
theorem was proved by Kenneth Blaha:

Theorem 9.6 Let G be a permutation group on n points, for which the minimum
base size is r. Then the greedy algorithm finds a base of size at most r(log log n+c)
for some absolute constant c.

Note that, for groups in the range of practical computation (up to, say, n = 104
or 105 ), log log n is smaller than 2.5, so effectively the result is within a constant
factor of the true value for such groups.
We begin with a lemma.

Lemma 9.7 Let G be a permutation group with a base of size r. Then any sub-
group H of G has an orbit of size at least |H|1/r .

Proof H has an orbit of size |H| on r-tuples, since there is an r-tuple (namely
the base) whose stabiliser is the identity. But this would not be possible if every
H-orbit had size smaller than |H|1/r .

Proof of the theorem First note that, by the Lemma, we have |G|1/r ≤ n, so
|G| ≤ nr . (This is easy to see directly.)
Use the greedy algorithm to choose r log log n points. Each point lies in an
orbit of size at least |H|1/r , where H is the stabiliser of the preceding points; so
|Hi | ≤ |Hi−1 |1−1/r . Thus, if K is the stabilsier of the chosen r log log n points, then
r log log n − log log n
|K| ≤ |G|(1−1/r) ≤ (nr )e = nr/ log n = er ,

(using (1 − 1/r)r ≤ e−1 ); so the choice of at most r log2 e base points by any
method brings us to the identity. So we get a base of size at most r log log n +
r log2 e.

91
Exercises
9.1. Which of the following permutation groups are IBIS groups?

• The rotation group of a regular polytope, acting on the faces.

• The symmetry group (rotations and reflections) of a regular polytope, acting
on the faces.
• The group of all permutations of a finite field F of the form x 7→ ax + b,
where a, b ∈ F and a 6= 0.
• The automorphism group of the Petersen graph, acting on its vertices.

9.2. Let C be the linear code over GF(2) spanned by the vectors (1, 1, 0) and
(1, 0, 1).

• Calculate the weight enumerator of C.

• Calculate the Tutte polynomial of the matroid M(C).
• Calculate the IBIS permutation group G associated with C, and find its cycle
index.
• Calculate the Tutte polynomial of the matroid associated with G.

9.3. The group of rotations of the cube is isomorphic to the symmetric group S4 .
We have seen two permutation actions of this group of degree 6: on the faces of
the cube, and on the 2-element subsets of {1, 2, 3, 4}. Show that both these per-
mutation groups of degree 6 are IBIS groups, and that the corresponding matroids
are isomorphic. Show also that the groups have different cycle indices. [Hence
the cycle index of an IBIS group is not in general determined by its matroid.]

92
10 Miscellanea
In this final section we treat a couple of miscellaneous topics, both in fact con-
nected with perfect codes: the construction of the binary Golay code, Witt system,
and Mathieu group; and the classification of solutions to “symmetric Sudoku”, in-
vented by Robert Connelly and independently by Vaughan Jones.

10.1 The Mathieu group M24 and its operands

The Mathieu group, the Golday code, and the Witt system are remarkable ob-
jects. They are one-offs, not part of a general theory. There are many ways of
constructing them, building up from below. But the road continues on, leading to
the Leech lattice and the Conway groups, then the Monster, with its connection
(called moonshine) with modular forms and conformal field theory.
Any construction of M24 works by starting with a suitable subgroup, building
from it a combinatorial object, and showing that this object has more symmetry
than the subgroup with which we began.

The extended Hamming code Recall the Hamming code, the [7, 4, 3] binary
code associated with the Fano plane, which we met in Part 1:
u
T
'$
u u
 T
b "T
 b" u"
b T
"" bbT
 &%
u
" u Tu
b

The Fano plane has a cyclic automorphism which is inherited by the Hamming
code, so we can write it in cyclic form, generated by 1101000 and its cyclic shifts.
We let H be the code obtained by adding an overall parity check. Thus H admits
an automorphism which permutes the first seven coordinates cyclically and fixes
the eighth. We now define H ∗ to be the code (also a [7, 4, 3] code) obtained by
reversing the first seven coordinates. Each of H and H ∗ contains the all-zero and
all-one words and 14 words of length 7, so their weight enumerators are X 8 +
14X 4Y 4 +Y 8 .
A short calculation shows that the intersection of H and H ∗ consists just of the
all-zero and all-one words.
Let G be the code with word length 24 defined by
G = {(a + x, b + x, a + b + x) : a, b ∈ H, x ∈ H ∗ }.

93
It is clear that G is a linear code.

G has dimension 12. For this it suffices to show that, if (a + x, b + x, a + b +

x) is the zero word, then a = b = x = 0. But our comment before the definition of
G shows that, if (a+x, b+x, a+b+x) = (0, 0, 0), then x = a = b = a+b ∈ H ∩H ∗ ,
so that x is the all-zero or the all-one word. But if x is all-1, then so are a, b and
a + b, which is impossible.

G is self-orthogonal (and hence self dual) For both H and H ∗ are self-dual,
and so

(a+x, b+x, a+b+x).(c+y, d +y, c+d +y) = a.y+c.x+b.y+d.x+(a+b).y+(c+d).x = 0.

G has minimum weight 8, and all weights are multiples of 4. An easy

calculation shows that if the weights of v and w are both divisible by 4 and v.w = 0,
then the weight of v + w is divisible by 4. Now G is generated by the words
(a, 0, a), (0, b, b) and (x, x, x), all of which have weights divisible by 4 and are
orthogonal; by induction, all weights in G are divisible by 4.
Suppose that G contains a word of weight 4, say (a + x, b + x, a + b + x). Note
that H and H ∗ are both orthogonal to the all-1 vector, so any vector in H + H ∗ has
even weight. Thus one of the three components of (a + x, b + x, a + b + x) must be
zero. Suppose that a + x = 0. Then x = a, and this is the all-zero or all-1 word. If
a + b + x = 0 then b = 0; otherwise a + b + x has weight at least four, so b + x = 0,
and we have a contradiction.
Now G contains the all-1 word of length 24, and so it has no words of weight
20 either.

G has weight enumerator X 24 + 759X 16Y 8 + 2576X 12Y 12 + 759X 8Y 16 +Y 24 .

We saw this earlier in the notes.

The Witt system Let X = {1, . . . , 24}, and let B be the set of subsets of X which
are the supports of words of weight 8 in G (that is, the sets of coordinates where
such words have non-zero entries).
Suppose that B1 , B2 ∈ B support words v1 and v2 , and that these have at least
five points in common. Then the symmetric difference of B1 and B2 is the support
of v1 + v2 , and has cardinality at most 6. This is impossible unless B1 = B2 . So
five points are contained in at most one element of B.

94
 But the average number of members of B which contain a given set of five
points is    
8 24
759 / = 1.
5 5
Thus any five points are contained in a unique block, and (X, B) is a Steiner
system S(5, 8, 24).

Uniqueness In this section we show first that a code with length 12, minimum
distance 8, containing the zero word, and having 212 codewords must be linear
and self-dual and have the same weight enumerator as G, and then that it must be
isomorphic to G.

Linearity Let C be such a code. Puncturing C at any position gives a code

C0 of length 23 with minimum distance 7 and 212 codewords. Since

223
23
23

= 212 ,
1 + 23 + 2 + 3

the code C0 is perfect – any word is at distance 3 or less from a unique codeword.
From this fact, the weight enumerator of C is easily deduced. Moreover, the same
argument applies to C + v for any v ∈ C, so this code also has weights divisible by
4; it follows that any two vectors in C have distance divisible by 4, so that C ⊆ C⊥ .
Since |C| = 212 we must have equality, which also shows that C is linear (since
C⊥ is linear for any code C).

Uniqueness A good construction often forms the basis of a uniqueness proof.

In this case, the construction is so simple that we have to work a bit harder to find
the uniqueness proof. I will give an outline.
Let C be a self-dual code of length 24 with weights 0, 8, 12, 16, 24. Let v be a
word of weight 8. Since all codewords meet v evenly, the code induced on B is the
even-weight code of length 8, with dimension 7. This means that the codewords
which vanish on B (the kernel projection of C onto the even-weight code) form
a 5-dimensional code, with minimum weight 8. Choosing a word of weight 8 in
this code, we get a partition of the 24 coordinates into three sets of 8, from which
we find that the code must be formed by the construction previously given.
Alternatively, identify the [16, 5, 8] code with the dual of the extended Ham-
ming code of length 16, and recover C from this.

95
 Uniqueness of S(5, 8, 24) Let S be a Steiner system S(5, 8, 24), and C the
code spanned by the characteristic functions of its blocks. A counting argument
shows that any two blocks of S meet in 0, 2 or 4 points, so C is self-orthogonal.
Another counting argument shows that it has more than 2048 words, so in fact it
is self-dual. So C is isomorphic to the Golay code (by the previous uniqueness
theorem), from which the uniqueness of S is immediate.

The Mathieu group The Golay code and the Witt system have the same auto-
morphism group, since the code is spanned by the blocks of the system, and these
blocks are the words of weight 8 in the code. This group is the Mathieu group
M24 .
I will not discuss it in detail, but remark that a good construction and unique-
ness proof allow us to derive properties of the group. Here, for example, is a proof
of its 5-transitivity.
The uniqueness proof can start with any block, so given any two blocks, there
is an automorphism carrying the first to the second. Now the code induced on a
block is the even-weight code of length 8, and any five of its points can be mapped
to any other five by a symmetry of the configuration. Now given two 5-tuples
(x1 , . . . , x5 ) and (y1 , . . . , y5 ), there are unique blocks B and C containing them, and
an automorphism g carrying B to C; then there is an automorphism h fixing C and
carrying xi g to yi for i = 1, . . . , 5. Now gh is the required automorphism carrying
xs to ys.

10.2 Symmetric Sudoku

Sudoku I assume that you are familiar with Sudoku, which was invented by
retired New York architect Howard Garns in 1979, popularised in Japan by Maki
Kaji, and then brought to the world by New Zealander Wayne Gould, brother of
former UK Labour MP Brian Gould.
Of course, there is a back story here. By the 1960s, statisticians working in
experimental design had assembled the essential ideas: Behrens had defined a
gerechte design, a Latin square divided into regions so that each symbol occurs
once in each region; and Nelder had defined a critical set in a Latin square to be a
set of entries from which the square can be reconstructed uniquely. Latin squares
themselves go back to Euler, who used them in a construction of magic squares,
a concept which has been studied for at least two millennia.
Sudoku has of course attracted the attention of mathematicians. Bertram Fel-

96
genhauer and Frazer Jarvis did a heroic computation to show that the number of
ways to fill the grid following the Sudoku rules is 6 670 903 752 021 072 936 960.
(It seems that they were not the first: someone known only as QSCGZ posted the
number as a comment on [Link] in 2003, with no indication of the proof.)
More recently, Gary McGuire, Bastian Tugemann and Gilles Civario showed that
the minimum number of entries in a Sudoku puzzle (with unique solution) is 17,
confirming a long-held belief.
In counting filled Sudoku grids, we may want to count up to some obvious
equivalences:

• We can permute the rows in three blocks of three, and permute the three
blocks among themselves; and similarly for the columns.
• We can transpose the square.
• We can permute the entries 1, . . . , 9 arbitrarily.

Frazer Jarvis and Ed Russell showed that, if we count up to these symmetries,

the number of distinct solutions is 5 472 730 538. They did this by the methods
we have studied in this course, in particular, the orbit-counting lemma. First we
classify elements of the group of possible symmetries described above. Then we
count the number of filled grids fixed by each type of symmetry. (For the identity
this is the result of Felgenhauer and Jarvis; fortunately, for other symmetries, the
number is smaller!)

Symmetric Sudoku This was invented by Robert Connelly, who told me about
it after giving a seminar on something quite different in Queen Mary University
of London. Independently, Vaughan Jones published a puzzle based on it in the
magazine of the Mathematical Sciences Research Institute in Berkeley. The pic-
ture below shows a symmetric Sudoku solution, turned into stained glass by David
Spiegelhalter, professor of public understanding of risk at the University of Cam-
bridge.

97
 Here it is in more familiar guise:

3 5 9 2 4 8 1 6 7
4 8 1 6 7 3 5 9 2
7 2 6 9 1 5 8 3 4
8 1 4 7 3 6 9 2 5
2 6 7 1 5 9 3 4 8
5 9 3 4 8 2 6 7 1
6 7 2 5 9 1 4 8 3
9 3 5 8 2 4 7 1 6
1 4 8 3 6 7 2 5 9

To understand the rules, we need to describe some more subsets. We use the
term fat column for the three columns corresponding to a column of 3 × 3 squares,
and minirow for a row of a 3 × 3 square. Similarly for fat row and minicolumn.
Now we define

• a broken row consists of the three minirows in the same position in their
3 × 3 squares (top, middle or bottom) in a fat column;
• a broken column consists of the three minirows in the same position in their
3 × 3 squares (left, middle or right) in a fat row;
• a location consists of the squares in a given position (top left, . . . , bottom
right) in their 3 × 3 squares.

98
 Now a symmetric Sudoko solution is a filled Sudoku grid in which each of the
numbers 1, . . . , 9 occurs precisely once in each row, once in each column, once in
each subsquare, once in each broken row, once in each broken column, and once
in each location.
You can check that the square given above satisfies these requirements.

Coordinatisation To analyse symmetric Sudoku, we first label each point of the

grid with a vector in a 4-dimensional vector space over GF(3) as follows:

• the first coordinate (0, 1 or 2) labels fat rows;

• the second coordinate labels rows within fat rows;
• the third coordinate labels fat columns;
• the fourth coordinate labels columns within fat columns.

So, for example, the cell in the top right of the middle 3 × 3 square has coordinates
(1, 0, 1, 2).
Now it is easy to see that the six distinguished regions in symmetric Sudoku
are given by the following equations:

• rows: x1 = a, x2 = b;
• columns: x3 = a, x4 = b;
• subsquares: x1 = a, x3 = b;
• broken rows: x2 = a, x3 = b;
• broken columns: x1 = a, x4 = b;
• locations: x2 = a, x4 = b.

Thus all combinations of two coordinates are covered.

We conclude that the nine positions of a given symbol have the property that
no two of them can agree in two coordinates. So, regarding their coordinates as
forming a code of length 4 over GF(3), we see that it has minimum distance 3,
and so is 1-error-correcting.
Furthermore, since
34

= 9,
1 + 2 41
we see that it achieves the sphere-packing bound, and so is a perfect code.

99
 It is not a hard exercise to show that any perfect 1-error-correcting code of
length 4 over GF(3) which contains 0 is linear, and so is a Hamming code: up to
column permutations and scalar multiplications, its generator matrix is
 
0 1 1 1
.
1 0 1 2

Our conclusion is:

A symmetric Sudoku solution corresponds to a partition of GF(3)4

into nine perfect codes.

So our final task is to study such partitions.

One solution is to take one linear perfect code; it is a 2-dimensional subspace
of a 4-dimensional vector space, so it has nine cosets, each of which is also a
perfect code, and these nine clearly form a partition. We call this “parallel type”,
since the nine cosets are parallel planes in the affine space.
It can be shown that there is one other solution up to symmetry. In the above
construction, we can find three of the cosets which partition a 3-dimensional sub-
space. Now we can find a different linear perfect code within this subspace and
replace the original three cosets by three cosets of this new code. This solution is
of “non-parallel type”. Our examples earlier are of this type.
The conclusion is:

Theorem 10.1 Up to permutations of rows and columns (preserving the sub-

squares), transposition, and arbitrary permutations of symbols, there are just two
symmetric Sudoku solutions.

100
Solutions to the exercises
(1.1) Over the binary field, two vectors are linearly independent if and only if
they are unequal and non-zero. For the only possible linear combinations with
coefficients not all zero are 0v1 + 1v2 = 0, 1v1 + 0v2 = 0, and 1v1 + 1v2 = 0. The
given matrix H has the property that all its columns are nonzero and no two equal.
So any two columns are linearly independent.
We saw that this implies that the code with parity check matrix H has mini-
mum distance (at least) 3, and so is 1-error-correcting.
It can be decoded with syndrome decoding as follows. Suppose that a word
w is received. Compute its syndrome wH > . If this is zero, then assume that w is
correct; otherwise, an error has occurred in the position whose base 2 representa-
tion is the syndrome. It can be shown that this gives the right answer provided it
is actually the case that at most one error has occurred.
For encoding, we need first to compute a generator matrix G, then encode the
message m as v = mG and transmit.
If H was in the form [−P> , Id ], then we would take G = [In−d , P], where n =
2d − 1. Since this is not so, we have to permute columns to get the last d columns
of H to carry an identity matrix (move columns 1, 2, 4, . . . , 2d−1 to the end), form
G, and then permute columns back again.
(1.2) This seems to have something to do with a 1-error correcting code over
the alphabet {0, +, −}, where + and − mean “heavier” and “lighter”. So let us
begin by writing down the parity check matrix of such a code from the preceding
question:
 
0 0 0 0 + + + + + + + + +
 0 + + + 0 0 0 + + + − − −
+ 0 + − 0 + − 0 + − 0 + −

Applying the syndrome decoding method should translate into performing weigh-
ings with coins marked + in the left-hand pan and coins marked − in the right.
But there are a few problems. Because we work mod 3 in the coding theory appli-
cation, the first weighing would balance if all the coins numbered 5–13 were in the
same pan! We have to fix this by arranging to have only eight coins in a weighing,
with four in each pan. So we will have to change the sign of some columns, and
delete one column.
The counts of +/− in the three rows are 9/0, 6/3, and 5/4. We start by
changing four signs to change the count to the first row to 5/4. To do this without

101
affecting the other rows, we want to choose pairs of columns which have either 00
or +− in the other rows: numbers 6 and 7, and 10 and 12, will do.
Next we fix the second row by changing the sign of the only column which is
zero in the other two rows, namely column 2.
Now each row has count 5/4, so deleting the all-+ column 9 finishes the job.
The resulting matrix is
 
0 0 0 0 + − − + − + − +
 0 − + + 0 0 0 + − − + −
+ 0 + − 0 − + 0 + 0 − −

or in other words, the weighing scheme is

• 5, 8, 10, 12 in left pan, 6, 7, 9, 11 in right;

• 3, 4, 8, 11 in left pan, 2, 9, 10, 12 in right;
• 1, 3, 7, 9 in left pan, 4, 6, 11, 12 in right.

Changing column signs and removing columns don’t change the property that any
two columns are linearly independent, so the code is still 1-error-correcting and
will do the job for us.
It is now straightforward to write down the syndromes for the 24 possible “er-
rors” (number of coin and whether light and heavy) and verify that different errors
have different syndromes (as expected), and to use the results of the weighings to
determine the “error”.
(1.3) A basis for C1 ⊕C2 consists of a basis for C1 (with the zero vector in C2
added at the end) and a basis for C2 (with the zero vector of C1 added at the start).
So the dimension is dim(C1 ) + dim(C2 ).
The weight of a word (c1 , c2 ) of the direct sum is equal to the sum of the
weights of c1 and c2 . So a non-zero word of minimum weight is obtained by
taking one of c1 and c2 to be zero, and the other to be of minimum weight in its
code.
This also shows that if C1 and C2 have respectively ai and bi words of weight
i, then the number of words of weight i in C1 ⊕C2 is
i
∑ a j bi− j .
j=0

But this is exactly the coefficient of X n−iY i in the product WC1 (X,Y )WC2 (X,Y ).

102
 (a) Suppose that dim(C1 ) ≤ dim(C2 ). Since they are vector spaces over the
same field, there is an injective linear map T : C1 → C2 . Take the code C =
{(c, cT ) : c ∈ C1 }. It is linear with dimension equal to that of C1 . Moreover,
for any non-zero c, the weights of c and cT are at least as big as the minimum
weights of C1 and C2 , and the weight of (c, cT ) is their sum.
(b) Do the construction suggested. Given a non-zero matrix of the specified
form, there are at least d1 non-zero columns, and each has at least d2 non-zero
entries, so the weight is at least d1 d2 . It is easy to construct a matrix with this
weight. (To form the code, just write all the matrix entries out in a single list.)
Suppose there was a general construction which produces the required code.
Give it as input the codes C1 = An1 and C2 = An2 consisting of all possible words
of the required weight. The output would have length and dimension both equal
to n1 + n2 , and so would be An1 +n2 . But this has minimum weight 1, whereas
d1 + d2 = 2.
(1.4) (a) We saw that, by taking a generator matrix of a linear code and putting
it into reduced echelon form, we obtain k columns (where k is the dimension)
which carry an identity matrix Ik . Encoding using this linear code, the k informa-
tion symbols will be written in these k positions. So the code is systematic.
(b) Suppose that a code is systematic. Take a set of k coordinate positions, and
take two k-tuples which agree in all but one of these positions. Their distance is
at most n − k + 1, since they can only differ in this one position and some of the
n − k positions outside the set.
Conversely, we show that no two words can have smaller distance. Take two
words with distance n − k or less. Then we can find k positions where they agree,
contradicting the fact that the code is systematic with respect to those positions.
(1.8) Clearly H1 is a [16, 8] code; by 2.3 its weight enumerator is

(X 8 + 14X 4Y 4 +Y 8 )2 = X 16 + 28X 12Y 4 + 198X 8Y 8 + 28x4Y 12 +Y 16 .

Moreover, it is self-dual since (v1 , v2 ).(w1 , w2 ) = v1 w1 + v2 w2 .

Consider C2 . There are 128 words of even weight and length 8, each of which
contributes two words to C2 ; so |C2 | = 256. We show that C2 ⊆ C2⊥ : this is just
a case of checking that any two words are orthogonal. There are four cases, of
which the first two are

• (v, v).(w, w) = 2v.w = 0,

• (v, v).(w, w + 1) = 2v.w + v.1 = 0,

103
using in the last step the fact that v has even weight.
Now C1 ⊆ hC1 i ⊆ C1⊥ , and dim(C1⊥ ) = 16 − dim(hC1 i) ≤ 8; so equality holds,
and C1 = C1⊥ . In particular, C1 is linear (this is not hard to show directly but it falls
out from this argument).
Counting weights, letting C be the even-weight code of length 8, C contains
• 0, giving one word of weight 0 and one of weight 8 in C2 ;
• 82 = 28 words of weight 2, giving 28 of weight 4 and 28 of weight 8 in C2 ;

• 84 = 70 words of weight 4, giving 140 words of weight 8 in C2 ;

• 86 words of weight 6, giving 28 of weight 12 and 28 of weight 4 in C2 ;

• 1, giving one of weight 16 and one of weight 8 in C2 .

Counting up gives the weight enumerator to be the same as for C1 .
Why are these codes different? Look at the supports of words of weight 4. For
C1 , these are contained in one or other of two disjoint sets of coordinates; but for
C2 they form a “connected hypergraph”.
(3.1) The first statement can be proved by induction on i; it is clear for i = 0.
Suppose it holds for i, and select i + 1 edges. The first i of them form a graph
with n − i components. The last edge cannot join two vertices in the same com-
ponent; for if v, w belong to the same component, then they are joined by a path,
and adding the edge {v, w} would create a cycle. So it joins vertices in different
components, thus reducing the number of components by 1.
Now the cluster expansion formula shows that
n−1  
n−1
PG (q) = ∑ (−1)i qn−i = q(q − 1)n−1 ,
i=0 i

by the Binomial Theorem.

(a) In any connected graph, we can order the vertices as v1 , . . . , vn so that for
any i, the subgraph on the first i vertices is connected. (At each stage, choose the
next vertex to be joined to some vertex chosen so far; if this were not possible, the
chosen vertices would be a union of connected components.) Now in a tree, vi+1
cannot be joined to more than one vertex in this set (for the same reason as in the
last proof). So there are q choices for the colour of v1 , and q − 1 choices for each
subsequent vertex. Multiplying these gives the same as above.
(b) A tree on more than one vertex has a leaf, a vertex v lying on only one edge
e = {v, w}. Deleting e gives the disjoint union of an isolated vertex and a tree on

104
n−1 vertices (with chromatic polynomial q2 (q−1)n−2 ), while contracting it gives
a tree on n−1 vertices (with chromatic polynomial q(q−1)n−2 ). Subtracting these
two polynomials gives the result.
(3.2) For 0 ≤ i ≤ n − 1, any i edges form a forest, with n − i components; so
we can use the Cluster Expansion.
Alternatively, if pn (q) denotes the chromatic polynomial of an n-cycle, we
have p3 (q) = q(q − 1)(q − 2) and

pn (q) = q(q − 1)n−1 − pn−1 (q).

Either method gives the result pn (q) = (q − 1)((q − 1)n−1 − (−1)n−1 ).

(3.3) Fix q, and choose any one of the PX1 (q) colourings of X1 . All the colours
in the set of size r are different, since the subgraph on this set is complete.
Now each of the PX2 (q) colourings of X2 with q colours also has the colours on
this set all different. By symmetry, each of the q(q−1) · · · (q−r +1) colourings of
the r-set occurs equally often; in particular, there are PX2 (q)/q(q−1) · · · (q−r +1)
colourings which agree with the chosen colouring of X1 on this set.
Combining such colourings of X1 and X2 gives a colouring of X, and every
colouring of X arises in this way. So the number of colourings of X is

PX1 (q)PX2 (q)/q(q − 1) · · · (q − r + 1).

(3.4) (a) Suppose there is no source; every vertex has an incoming directed
edge. Take a vertex v1 . Choose v2 with an edge v2 ← v1 . Continue. At some
point we meet a vertex seen before, at which point we have a directed cycle, a
contradiction.
(b) No two sources can be joined by an edge, since it would have to be directed
into one of them. So the colour classes contain no edges, and we have a proper
colouring.
(c) Clearly we cannot colour with fewer than χ(X) colours.
Another way of describing the colour classes is that the ith class is the set of
vertices v for which the longest directed path ending at v has length i. (Inductively,
all vertices ending directed paths with fewer than i vertices lie in the first i − 1
classes, so the claim holds.) Now it is clear that the number of colours required
does not exceed the number of vertices on a longest path in the graph.
(d) This is a little harder, but here is a warm-up. The value χ(X) is attained:
choose a colouring with d = χ(X) colours c1 , . . . , cd , and direct edges from ci to
c j whenever i < j. We may not recover the original colouring, but we cannot

105
use fewer colours. Also the value l(X) is attained: number the vertices along the
path from 1 to l(X), and the remaining vertices arbitrarily, and direct edges from
smaller to larger index: then inductively the ith vertex is put into the ith class for
i ≤ l(X), so at least this many classes are required.
(4.1) The group in question is the group of order 8 consisting of four rotations
and four turnings-over about lines of symmetry.
Number the squares of glass as shown:

1 2 3

4 5 6

7 8 9

As in examples we have seen before, a colouring is fixed by a permutation if

and only if the colours are constant on the cycles of the permutation. We have the
following kinds of permutation:

Type of symmetry Number Cycles of typical element

Identity 1 (1)(2)(3)(4)(5)(6)(7)(8)(9)
◦
180 rotation 1 (1, 9)(2, 8)(3, 7)(4, 6)(5)
90◦ rotation 2 (1, 3, 9, 7)(2, 6, 8, 4)(5)
horiz/vert flip 2 (1, 3)(2)(4, 6)(5)(7, 9)(8)
diagonal flip 2 (1)(5)(9)(2, 4)(3, 7)(6, 8)

Now we have to do nine separate calculations, one for each value of k. Here
9

is the calculation for k = 5, where there are 5 = 126 possible windows.
• The identity fixes all 126.
• For the 180◦ rotation, the five red squares must include the fixed point and
two of the four 2-cycles, so 6 fixed windows.
• For the 90◦ rotations, the five red squares must be the fixed point and one
cycle, so 2 fixed windows.
• For either type of flip (they have the same cycle structure), a fixed window
has either the three fixed points and one of the three 2-cycles, or one fixed
point and two 3-cycles, so 1 · 3 + 3 · 3 = 12 fixed windows.

106
The Orbit-counting Lemma shows that the number of orbits is
1
(126 + 6 + 2 · 2 + 4 · 12) = 23,
8
and one window from each orbit requires 23 · 5 = 115 red squares.
So k = 5 satisfies the conditions of the problem.
Now you can either repeat the calculation for other values of k and find that
no other value works, or argue that the statement of the problem requires a unique
solution and so it must be 5. [Or wait until we have learned about the cycle index,
which enables all of these numbers to be computed simultaneously.]
(4.2) By the Orbit-counting Lemma, the average number of fixed points of
elements of G is 1. The identity fixes |X| points, and |X| > 1 (given), so some
element fixes fewer than one point, that is, no points!
(4.3) (a) We found a group of automorphisms of order 120; we have to show
that there are no more. There are 10 · 3 · 2 · 2 ways to choose a path with three
vertices in the graph, and it is not hard to show that no automorphism can fix such
a path. (If it fixes a vertex and two of its neighburs, it must fix the third neighbour
also; and since any two non-adjacent points have a unique common neighbour,
an automorphism fixing two such points must fix their neighbour.) So different
automorphisms map such a path to different places, and there cannot be more than
120 automorphisms.
(b) A vertex v has (at most) three neighbours. Each has (at most) three neigh-
bours, one of which is v, so at most two neighbours not yet accounted for. Since
no vertex is further than two steps from v, this is everything, and there are at most
1 + 3 + 6 = 10 vertices. The uniqueness proof is below.
(c) A vertex v has (at least) three neighbours. Each has (at least) three more
neighbours, one of which is v, and the others are all new (else there is a 3-cycle)
and all distinct (else there is a 4-cycle). So there are at least 1+3+6 = 10 vertices.
Again the uniqueness proof is below.
(d) Trial and error.
(e) The uniqueness proof. A graph meeting the bounds in (b) or (c) has con-
stant valency 3, diameter 2, and girth 5.
Choose an edge {x, y}. Let A be the set of neighbours of x other than y, and
B the set of neighbours of y other than x, so |A| = |B| = 2. Any further vertex is
at distance 2 from x and y, and so is joined to one neighbour of each; label such a
vertex (a, b) if it is joined to a ∈ A and b ∈ B. Exactly one vertex has each label.
(If there were more than one, they would form a 4-cycle with a and b; if there

107
were none, then a and b would have no common neighbour.) So we now have
2 + 4 + 4 = 10 vertices and 1 + 4 + 8 = 13 edges, so there are just two more edges,
which must join vertices with labels of the form (a, b).
Suppose that A = {a1 , a2 } and B = {b1 , b2 }. Then (a1 , b1 ) cannot be joined to
either (a1 , b2 ) or (a2 , b1 ) (this would create a triangle), and so must be joined to
(a2 , b2 ). Similarly (a1 , b2 ) is joined to (a2 , b1 ). Now we have everything.
(4.4) Boring calculation.
(4.5) Since there are no edges, we can apply the colours arbitrarily, so there
are qn altogether. We can think of this as selecting a sample of colours of size n,
in order.
If we don’t care about the order of the colours, we are choosing an unordered
sample of n things
from a set of q with repetitions allowed; the number of such
samples is q+n−1
n , as required.
(6.1) The question asks: for which values of n and r is there a graph with n
vertices with the property that the shortest cycle has length r + 1 and any r + 1
edges form a cycle?
Clearly such a graph exists for r = 1 (n loops on a single vertex), for r = 2 (n
parallel edges joining two vertices), or for r = n (a tree), or for r = n − 1 (a cycle
with n vertices).
We will show that there are no others. So suppose that 2 < r < n − 1 and let X
be a graph with this property. Then there are no loops or parallel edges in X, since
r > 2. Choose r + 2 distinct edges e1 , . . . , er+2 (possible since r < n − 1). Then
e1 , . . . , er+1 form a cycle, and so e1 , . . . , er form a path. But e1 , . . . , er , er+2 also
form a cycle, so er+1 and er+2 must both join the ends of the path, and so they are
parallel edges, a contradiction.
(6.2) We saw that, if X is a graph with connected components X1 and X2 , and
Y is the graph obtained by identifying a vertex in X1 with a vertex in X2 , then the
graphic matroids M(X) and M(Y ) are isomorphic. If X has just two components
then Y is connected.
For the second part, note that this process can be done in different ways, so
producing different connected graphs with the same matroid. For example, any
two trees with the same number of edges have isomorphic (free) matroids.
(6.3) (a) Since M(X) is a uniform matroid Un,n−1 , we have
n−1
xn − 1
TM(X) (x, y) = ∑ (x − 1)n−1−i + (y − 1) = x−1
+ (y − 1).
i=0

108
Then the chromatic polynomial is

PX (q) = (−1)n−1 qTM(X) (1 − q, 0) = (q − 1)n + (−1)n (q − 1).

(b) Deleting an edge from the n-cycle Cn gives a tree, with chromatic polyno-
mial q(1 − 1)n−1 . Contracting an edge gives the (n − 1)-cycle. So if pn (q) is the
chromatic polynomial of an n-cycle, then

pn (q) = q(q − 1)n−1 − pn−1 (q).

This determines pn recursively starting with p3 (q) = q(q−1)(q−2). It is a routine

exercise to show that the polynomial computed under (a) satisfies this recursion.
(7.1) (Compare Exercise 1.6.) An [n, k] code is MDS if and only if every set
of k coordinates is systematic, that is, every k-set of columns is a basis. This
precisely says that the matroid is uniform Un,k .
(7.2) The Tutte polynomial of Un,3 is
   
3 2 n n
TM (x, y) = (x − 1) + n(x − 1) + (x − 1) + + ∑ (y − 1)n−4 .
2 3 i≥4

The weight enumerator of the code now comes from Greene’s theorem:
 
n−3 3 X + (q − 1)Y X
WC (X,Y ) = Y (X −Y ) T , .
X −Y Y
I am not going to work this out.
Finding an example is quite tricky. Here is a 3 × q matrix in which every three
columns are linearly independent. Let GF(q) = {a0 , . . . , aq−1 }. Then put
 
1 1 ... 1
A =  a0 a1 . . . aq−1  .
a20 a21 . . . a2q−1
Any three columns form a Vandermonde matrix
 
1 1 1
 x y z ,
x2 y2 z2

whose determinant is (x − y)(y − z)(z − x), which is non-zero when x, y, z are all
distinct.

109
 Now we can extend this matrix by adding an extra column
 
0
0.
1
Any three columns including this one have determinant equal to that of a 2 × 2
Vandermonde matrix, so non-zero.
(9.1) (a) The stabiliser of a face is the cyclic group of rotations about the axis
through the centre of that face. It fixes the opposite face (in all cases except the
tetrahedron) and moves all other faces. It is clear that the stabiliser of any face not
opposite the first is trivial. So this is an IBIS group of rank 2.
(b) In the symmetry group, the stabiliser of two non-opposite faces contains
a reflection in the plane containing the two rotation axes, provided that this is a
plane of symmetry. So if it is, then a third face has to be fixed to obtain a base.
With the help of models of the polyhedra, you can check that this is true in all
cases except the icosahedron, which has some pairs of faces for which this is true
and some for which it is not. So the icosahedral symmetry group has irredundant
bases of sizes 2 and 3 and is not an IBIS group; the other symmetry groups are
IBIS groups.
(c) The group has order q(q − 1), so no base can have size 1. But if we fix two
distinct points x and y, then the coefficients a and b of the map must satisfy

ax + b = x, ay + b = y,

from which we find that a = 1 and b = 0, and so the only such map is the
identity. So every 2-element set is an irredundant base, and G is an IBIS group.
(d) This group is not an IBIS group. The stabiliser of three points mutually at
distance 2 is trivial, but the stabiliser of three points on a path of length 2 is not.
(Check this on a diagram.)
(9.2) The codewords are 000, 110, 101 and 011, so the weight enumerator is
X 3 + 3XY 2 .
(b) Any two points are independent, so the matroid is U3,2 , with Tutte polyno-
mial (x − 1)2 + 3(x − 1) + 3 + (y − 1) = x2 + x + y.
Further exercise: Check Greene’s theorem for this example.
(c) Number the points as follows:

1 = (1, 0), 2 = (1, 1), 3 = (2, 0), 4 = (2, 1), 5 = (3, 0), 6 = (3, 1).

110
Now the identity fixes all six points, and the permutations associated with the
other codewords are:
110 (1, 2)(3, 4)
101 (1, 2)(5, 6)
011 (3, 4)(5, 6).
The cycle index is 14 (s61 + 3s21 s22 .
(d) The bases of the matroid are all sets of size 2 except for {1, 2}, {3, 4} and
{5, 6}.
Any set of size 3 or greater has rank 2. So the Tutte polynomial is

(x−1)2 +6(x−1)+3(x−1)(y−1)+12+20(y−1)+15(y−1)2 +6(y−1)3 +(y−1)4 .

If you want, you may check Proposition 9.3 here.

(9.3) We saw in Question (9.1) that the rotation group of a cube is an IBIS
group. The group induced by S4 on 2-element subsets of {1, 2, 3, 4} is also an
IBIS group, since the stabiliser of {1, 2} fixes {3, 4}, while additionally fixing
{x, y} for any x ∈ {1, 2} and y ∈ {3, 4} gives the identity.
Both matroids are a 2-fold inflation of U3,2 : the elements are partitioned into
three sets of size 2 and the bases are all pairs of elements from different parts of
the partition.
We computed the cycle indices of these groups earlier.

111