MA3J215 Combinatorics II
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 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.
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 SauerShelah Lemma.
 Symmetric functions, Young Tableaux.
 Designs and codes: Latin squares, finite projective planes, errorcorrecting 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 3APs 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.
Study time
Type  Required 

Lectures  30 sessions of 1 hour (20%) 
Tutorials  9 sessions of 1 hour (6%) 
Private study  111 hours (74%) 
Total  150 hours 
Private study description
Review lectured material and work on set exercises.
Costs
No further costs have been identified for this module.
You do not need to pass all assessment components to pass the module.
Assessment group B
Weighting  Study time  

Inperson Examination  100%  
A 3hour written exam.

Assessment group R
Weighting  Study time  

Inperson Examination  Resit  100%  

Feedback on assessment
Support classes, work returned after marking and exam feedback.
Courses
This module is Optional for:
 Year 1 of TMAAG1PD Postgraduate Taught Interdisciplinary Mathematics (Diploma plus MSc)
 Year 1 of TMAAG1PC Postgraduate Taught Mathematics (Diploma plus MSc)

UCSAG4G1 Undergraduate Discrete Mathematics
 Year 3 of G4G1 Discrete Mathematics
 Year 3 of G4G1 Discrete Mathematics
 Year 3 of UCSAG4G3 Undergraduate Discrete Mathematics
 Year 4 of UCSAG4G4 Undergraduate Discrete Mathematics (with Intercalated Year)
 Year 4 of UCSAG4G2 Undergraduate Discrete Mathematics with Intercalated Year

USTAG300 Undergraduate Master of Mathematics,Operational Research,Statistics and Economics
 Year 3 of G300 Mathematics, Operational Research, Statistics and Economics
 Year 4 of G300 Mathematics, Operational Research, Statistics and Economics
 Year 3 of UMAAGL11 Undergraduate Mathematics and Economics
This module is Core option list B for:

UMAAGV17 Undergraduate Mathematics and Philosophy
 Year 3 of GV17 Mathematics and Philosophy
 Year 3 of GV17 Mathematics and Philosophy
 Year 3 of GV17 Mathematics and Philosophy
 Year 3 of UMAAGV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations
This module is Core option list D for:

UMAAGV18 Undergraduate Mathematics and Philosophy with Intercalated Year
 Year 4 of GV18 Mathematics and Philosophy with Intercalated Year
 Year 4 of GV18 Mathematics and Philosophy with Intercalated Year
 Year 4 of UMAAGV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations
This module is Option list A for:

TMAAG1PD Postgraduate Taught Interdisciplinary Mathematics (Diploma plus MSc)
 Year 1 of G1PD Interdisciplinary Mathematics (Diploma plus MSc)
 Year 2 of G1PD Interdisciplinary Mathematics (Diploma plus MSc)
 Year 1 of TMAAG1P0 Postgraduate Taught Mathematics

TMAAG1PC Postgraduate Taught Mathematics (Diploma plus MSc)
 Year 1 of G1PC Mathematics (Diploma plus MSc)
 Year 2 of G1PC Mathematics (Diploma plus MSc)

UMAAG105 Undergraduate Master of Mathematics (with Intercalated Year)
 Year 3 of G105 Mathematics (MMath) with Intercalated Year
 Year 4 of G105 Mathematics (MMath) with Intercalated Year
 Year 5 of G105 Mathematics (MMath) with Intercalated Year

UMAAG100 Undergraduate Mathematics (BSc)
 Year 3 of G100 Mathematics
 Year 3 of G100 Mathematics
 Year 3 of G100 Mathematics

UMAAG103 Undergraduate Mathematics (MMath)
 Year 3 of G100 Mathematics
 Year 3 of G103 Mathematics (MMath)
 Year 3 of G103 Mathematics (MMath)
 Year 4 of G103 Mathematics (MMath)
 Year 4 of G103 Mathematics (MMath)

UMAAG106 Undergraduate Mathematics (MMath) with Study in Europe
 Year 3 of G106 Mathematics (MMath) with Study in Europe
 Year 4 of G106 Mathematics (MMath) with Study in Europe
 Year 4 of USTAG1G3 Undergraduate Mathematics and Statistics (BSc MMathStat)
 Year 5 of USTAG1G4 Undergraduate Mathematics and Statistics (BSc MMathStat) (with Intercalated Year)

USTAGG14 Undergraduate Mathematics and Statistics (BSc)
 Year 3 of GG14 Mathematics and Statistics
 Year 3 of GG14 Mathematics and Statistics
 Year 4 of UMAAG101 Undergraduate Mathematics with Intercalated Year

USTAY602 Undergraduate Mathematics,Operational Research,Statistics and Economics
 Year 3 of Y602 Mathematics,Operational Research,Stats,Economics
 Year 3 of Y602 Mathematics,Operational Research,Stats,Economics
This module is Option list B for:
 Year 1 of TMAAG1PE Master of Advanced Study in Mathematical Sciences
 Year 3 of USTAG1G3 Undergraduate Mathematics and Statistics (BSc MMathStat)
 Year 4 of USTAG1G4 Undergraduate Mathematics and Statistics (BSc MMathStat) (with Intercalated Year)
 Year 4 of USTAGG17 Undergraduate Mathematics and Statistics (with Intercalated Year)
This module is Option list E for:

USTAG300 Undergraduate Master of Mathematics,Operational Research,Statistics and Economics
 Year 3 of G30D Master of Maths, Op.Res, Stats & Economics (Statistics with Mathematics Stream)
 Year 4 of G30D Master of Maths, Op.Res, Stats & Economics (Statistics with Mathematics Stream)

USTAG301 Undergraduate Master of Mathematics,Operational Research,Statistics and Economics (with Intercalated
 Year 3 of G30H Master of Maths, Op.Res, Stats & Economics (Statistics with Mathematics Stream)
 Year 4 of G30H Master of Maths, Op.Res, Stats & Economics (Statistics with Mathematics Stream)
 Year 5 of G30H Master of Maths, Op.Res, Stats & Economics (Statistics with Mathematics Stream)