University of St Andrews University of St Andrews

MT5821: Advanced Combinatorics

Scottish Combinatorics Meeting
This two-day meeting takes place in Edinburgh on
26 and 27 April. Accordingly there will
be no lecture on 27 April, but you are encouraged to
have an educational outing to Edinburgh.
The conference web page is here.
First lecture 11:00 (Thu), 09:45 (Fri).

Week 11
There will be no lecture on 27 April
(Friday of Week 11) because of the
SCM (see above).
The plan is to have a lecture on the
binary Golay code and associated Steiner
systems and Mathieu groups on Monday,
and a revision lecture on Wednesday.
Please suggest topics for the revision
lecture to me by email, or bring along
your questions to the lecture!

Exam
Monday 21 May 2018
14:00–16:30
Younger Hall

The module

The module will run in Semester 2 (January to April 2018).

Lectures: Mondays (odd weeks), Wednesdays, Fridays, 12:00-13:00, 1A

Tutorials: Mondays (not week 1), 15:00-16:00, 3B

The module descriptor is here. As you will see, this allows some flexibility. I propose that this year, we will do syllabus 2 (combinatorial polynomials). This will include chromatic polynomial, Tutte polynomial, cycle index, orbital chromatic polynomial, weight enumerator, etc. A course information sheet is available here.

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

Here are the notes for the special lecture on 16 March.

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.

I should make clear that, while some ideas from coursework problems may reappear in exam questions, they are not to be regarded as of comparable difficulty. In the exam your time is strictly limited, but for coursework you can spend as long as you like on the problems, so they will naturally be more challenging.

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
10 April 2018