Introductory description

This course follows on from the second year combinatorics course. It has two main parts: a section on graph theory that builds on what appears in the earlier course: and a section which deals with a variety of combinatorial structures with special properties and symmetries. On the one hand the course introduces more advanced combinatorial methods and on the other it explains how combinatorics connects with other areas of maths, such as geometry, probability, algebra and number theory, and also with computer science.

Module web page

Module aims

Outline syllabus

This is an indicative module outline only to give an indication of the sort of topics that may be covered. Actual sessions held may differ.

• Partially ordered sets and set systems: Dilworth's theorem, Sperner's theorem, the LYM inequality, the Sauer-Shelah Lemma.
• Symmetric functions, Young Tableaux.
• Designs and codes: Latin squares, finite projective planes, error-correcting codes.
• Colouring: the chromatic polynomial,
• Geometric combinatorics: Caratheodory's Theorem, Helly's Theorem, Radon's Theorem.
• Probabilistic method: the existence of graphs with large girth and high chromatic number, use of concentration bounds.
• Matroid theory: basic concepts, Rado's Theorem.
• Regularity method: regularity lemma without a proof, the existence of 3-APs in dense subsets of integers.

Learning outcomes

By the end of the module, students should be able to:

• state and prove particular results presented in the module
• adapt the presented methods to other combinatorial settings
• apply simple probabilistic and algebraic arguments to combinatorial problems
• use presented discrete abstractions of geometric and linear algebra concepts
• derive approximate results using the regularity method

Indicative reading list

R. Diestel: Graph Theory, Springer, 4th edition, 2012. R. Stanley: Algebraic Combinatorics: Walks, Trees, Tableaux and More, Springer, 2013.

Subject specific skills

Students will meet and understand combinatorial methods and structures. They will see how these can be applied to problems in geometry and computer science as well as understanding them in their own right.

Transferable skills

Like all mathematics courses this one teaches students to think clearly, construct reasoned arguments and to spot logical flaws. The section on random graphs provides an extremely potent way of thinking about phenomena in the real world: by studying the typical or random examples rather than specific ones. The section on codes introduces students to a specific tool used throughout industry and communications: in the manufacture of CDs, DVDs and communications networks.