Skip to main content

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. 


Additional Resources

Archived Pages: 2015 2016 2017

yr1.jpg
Year 1 regs and modules
G100 G103 GL11 G1NC

yr2.jpg
Year 2 regs and modules
G100 G103 GL11 G1NC

yr3.jpg
Year 3 regs and modules
G100 G103

yr4.jpg
Year 4 regs and modules
G103

Archived Material
Past Exams
Core module averages