# MA3J2 Combinatorics II

**Lecturer: **Keith Ball

**Term(s): **Term 2

**Status for Mathematics students: **List A

**Commitment: **30 Lectures

**Assessment: **Summer exam (100%)

**Prerequisites: **MA241 Combinatorics

**Leads To: **MA4J3 Graph Theory

**Content: **Some or all of the following topics:

• 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.

**
Aims:
**To give the students an opportunity to learn some of the more advanced combinatorial methods, and to see combinatorics in a broader context of mathematics.

**
Objectives:
** By the end of the module the student 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

**
Books:
**R. Diestel: Graph Theory, Springer, 4th edition, 2012.

R. Stanley: Algebraic Combinatorics: Walks, Trees, Tableaux and More, Springer, 2013.