Three years ago, when I joined the School of Mathematics and Statistics at the University of St Andrews, it was suggested that I might like to give a final year MMath module on “Advanced Combinatorics”. No compulsion.
Well, of course I liked. So, could I write out a syllabus and we will get it approved. Trouble was, of course, I couldn’t decide exactly what I wanted to talk about. So I wrote out three syllabuses, and suggested that the Director of Teaching should choose the most appropriate one. The response was, “We will approve all three, and you can give whichever one you like”.
Wonderful flexibility. I was delighted to have come to a university where such things were still possible in this over-bureaucratic age of higher education.
Anyway, three years have passed by, and I have just come to the end of lectures on the third of the topics. So I have compiled the lecture notes into three files and put them in my lecture note collection here. If they might be of any use to you, for either learning or teaching, please take a look.
So what is there?
Part 1 is on enumerative combinatorics. You will find elementary counting (with short digressions on Ramsey’s theorem and Steiner systems), formal power series, linear recurrences, Catalan objects, Gaussian coefficients, Möbius inversion, number partitions (up to Jacobi’s triple product identity), set partitions and permutations. Not much asymptotics, but there is a proof of Stirling’s formula (how could I not do this, living in Scotland?). Also in honour of my new place of residence, at Ursula Martin’s suggestion I renamed the pigeonhole principle the “doocot principle” – you see many old doocots standing in gardens and fields around east Fife.
Part 2 is entitled “Structure, symmetry and polynomials”. The most important structural polynomial is the Tutte polynomial of a matroid, which specialises to the chromatic polynomial of a graph and to the weight enumerator of a linear code. To measure symmetry, we have the cycle index polynomial of a permutation group, a way to codify the Orbit-Counting Lemma. One of my long-term interests is to try to combine these two strands, and there is some material on this. Diversions cover codes over the integers mod 4, IBIS groups, Mathieu groups, and symmetric Sudoku. It was for this version of the module that I was awarded a teaching innovation prize.
Part 3 is on finite geometry (loosely interpreted) and strongly regular graphs. The course begins with two classic theorems: the Friendship theorem, and Moore graphs of diameter 2, as a warmup to what proved a central theme of the course: the classification of graphs with the “strong triangle property”. After a discussion of projective planes and designs, I give the classification of the ADE root systems (using the Goethals–Seidel approach) and apply this to the classification of graphs with least eigenvalue −2 or greater. Then more finite geometry: projective spaces, generalised quadrangles (those with three points on a line are classified by the central theme), generalised polygons, and finally polar spaces, where the central theme is generalised using Jonathan Hall’s proof of the Shult–Seidel theorem on graphs with the “triangle property”. Diversions include partitioning complete graphs into strongly regular graphs, with application to the Ramsey number R(3,3,3).
All parts are self-contained, though it often occurs that a topic mentioned in one part is discussed in more detail in another. All parts include exercises after each section and solutions to most of the exercises at the end.
The notes are a bit rough; I have not had time for careful proofreading and editing. But I hope they may be of some use.
Peter Cameron's Blog 