# MA3J2 Combinatorics II

**Lecturer: **Keith Ball

**Term(s): **Term 1

**Status for Mathematics students: **List A

**Commitment: **30 Lectures

**Assessment: **100% Examination

**Formal registration prerequisites: **None

**Assumed knowledge: **

- Graph theory
- Hall's Theorem
- Graph colouring

MA260 Norms, Metrics and Topology or MA222 Metric Spaces:

- Norms on Euclidean space
- Open and closed sets
- Compactness

MA249 Algebra II: Groups and Rings:

- Basic examples of finite fields

- Events
- Probabilities
- Random variables

**Useful background: **

- Poisson distribution
- Chebyshev's inequality
- The Central Limit Theorem

- Projective geometry

**Synergies: **The following module goes well together with Combinatorics II:

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