Skip to main content Skip to navigation

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:

MA241 Combinatorics I:

  • 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

ST111 Probability A:

  • Events
  • Probabilities
  • Random variables

Useful background:

ST112 Probability B:

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

MA243 Geometry:

  • Projective geometry

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

MA3G7 Functional Analysis I

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