University of St Andrews University of St Andrews

MT5821: Advanced Combinatorics


The module

The module ran in Semester 2 (January to April 2018). This page will be taken down shortly.

Exam resources

Normally I would post the exam paper from last time this version of the module was given. However, the file seems to have disappeared. Apologies for this. In its place, here is a file which contains preliminary versions of the questions which were on the exam paper and also those on the sample exam paper that was provided in 2015. The syllabus then was not quite the same as this year's, so there will be a couple of unfamiliar topics in these questions. And here is the actual sample exam.

Hopefully these will give you a taste of the real thing.

Teaching material

  1. Coding theory
  2. Binomial coefficients
  3. Graph colouring
  4. Counting up to symmetry
  5. Matroids
  6. Tutte polynomial
  7. Matroids and codes
  8. Cycle index
  9. Permutation group bases and IBIS groups
  10. Miscellanea*
  11. Balls in boxes*

*A single lecture on Miscellanea covered the Golay code, Witt system and Mathieu group on 24 points. The notes also include an application of coding theory to symmetric Sudoku. The lecture on Balls in boxes was given on 16 March as an application of the Cycle Index Theorem.

Problems and solutions

Problems are posted here for you to try. I strongly urge you to have a go. Some of them are easy, some are much more difficult! You are not expected to solve all of the problems. Any written work handed in will be marked and handed back to you with as quick a turnaround time as I can manage. Solutions will be posted here later.

Miscellany

Materials for the other syllabuses are available: enumerative combinatorics, finite geometries.

Here is a problem for you to try. No special knowledge required.

Problem
Let f be a polynomial which takes integer
values on all the non-negative integers. Show
that f takes integer values on all integers.

Peter J. Cameron
Room 317, Mathematical Institute
pjc20@st-andrews.ac.uk
5 June 2018