MA3J2-15 Combinatorics II

Department
Warwick Mathematics Institute
Level
Credit value
15
Module duration
10 weeks
Assessment
Multiple
Study location
University of Warwick main campus, Coventry

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

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
In-person Examination 100%

A 3-hour written exam.

• Answerbook Gold (24 page)
Assessment group R
Weighting Study time
In-person Examination - Resit 100%
• Answerbook Gold (24 page)
Feedback on assessment

Support classes, work returned after marking and exam feedback.

Courses

This module is Optional for:

• Year 1 of TMAA-G1PD Postgraduate Taught Interdisciplinary Mathematics (Diploma plus MSc)
• Year 1 of TMAA-G1PC Postgraduate Taught Mathematics (Diploma plus MSc)
• UCSA-G4G1 Undergraduate Discrete Mathematics
• Year 3 of G4G1 Discrete Mathematics
• Year 3 of G4G1 Discrete Mathematics
• Year 3 of UCSA-G4G3 Undergraduate Discrete Mathematics
• Year 4 of UCSA-G4G4 Undergraduate Discrete Mathematics (with Intercalated Year)
• Year 4 of UCSA-G4G2 Undergraduate Discrete Mathematics with Intercalated Year
• USTA-G300 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 UMAA-GL11 Undergraduate Mathematics and Economics

This module is Core option list B for:

• UMAA-GV17 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 UMAA-GV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations

This module is Core option list D for:

• UMAA-GV18 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 UMAA-GV19 Undergraduate Mathematics and Philosophy with Specialism in Logic and Foundations

This module is Option list A for:

• TMAA-G1PD 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 TMAA-G1P0 Postgraduate Taught Mathematics
• TMAA-G1PC Postgraduate Taught Mathematics (Diploma plus MSc)
• Year 1 of G1PC Mathematics (Diploma plus MSc)
• Year 2 of G1PC Mathematics (Diploma plus MSc)
• UMAA-G105 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
• UMAA-G100 Undergraduate Mathematics (BSc)
• Year 3 of G100 Mathematics
• Year 3 of G100 Mathematics
• Year 3 of G100 Mathematics
• UMAA-G103 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)
• UMAA-G106 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 USTA-G1G3 Undergraduate Mathematics and Statistics (BSc MMathStat)
• Year 5 of USTA-G1G4 Undergraduate Mathematics and Statistics (BSc MMathStat) (with Intercalated Year)
• USTA-GG14 Undergraduate Mathematics and Statistics (BSc)
• Year 3 of GG14 Mathematics and Statistics
• Year 3 of GG14 Mathematics and Statistics
• Year 4 of UMAA-G101 Undergraduate Mathematics with Intercalated Year
• USTA-Y602 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 TMAA-G1PE Master of Advanced Study in Mathematical Sciences
• Year 3 of USTA-G1G3 Undergraduate Mathematics and Statistics (BSc MMathStat)
• Year 4 of USTA-G1G4 Undergraduate Mathematics and Statistics (BSc MMathStat) (with Intercalated Year)
• Year 4 of USTA-GG17 Undergraduate Mathematics and Statistics (with Intercalated Year)

This module is Option list E for:

• USTA-G300 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)
• USTA-G301 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)