MTH711U: Extremal Combinatorics, Autumn 2011

This is a level 7 course that ran in Autumn term 2011. In brief:

How many edges can a graph have without containing a triangle? How large can a family of k-element subsets of an n-element set be if any two of them have non-empty intersection? These questions fit the bill of an extremal question in combinatorics, seeking to determine the extreme value of some parameter over a class of combinatorial structures. This module will cover results of this flavour on both graphs and set systems, including answers to the above questions (through Mantel's theorem and the Erdős-Ko-Rado theorem respectively). There will be an emphasis on techniques as well as results, including the use of linear algebra, probabilistic methods and compressions.

Course description and information


Examples sheets will be posted here after being distributed in class.

  1. Examples sheet 1, distributed on 04/10/2011. (Updated 14/10/2011 — typos corrected.)
  2. Examples sheet 2, distributed on 18/10/2011. (Updated 20/10/2011 — clarified Q1.)
  3. Examples sheet 3, distributed on 01/11/2011. (Updated 07/11/2011 — typo corrected.)
  4. Examples sheet 4, distributed on 15/11/2011.
  5. Examples sheet 5, final examples sheet.
Past exam papers. The corresponding courses differed slightly from this one in the details, but were largely similar.
Updated 02 Jan 2012