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
- The official course details can be found from the department's module listings.
- Lectures: Tuesdays 11 am – 1 pm in room 203 (maths). (Departmental timetables.)
- Tutorials: Tuesdays 10 am – 11 am.
- Lecturer: Olof Sisask, room 113 (maths). Please send me an e-mail to agree on a time if you wish to talk about anything to do with the course; .
Examples sheets will be posted here after being distributed in class.
Past exam papers. The corresponding courses differed slightly from this one in the details, but were largely similar.
- Examples sheet 1, distributed on 04/10/2011. (Updated 14/10/2011 — typos corrected.)
- Examples sheet 2, distributed on 18/10/2011. (Updated 20/10/2011 — clarified Q1.)
- Examples sheet 3, distributed on 01/11/2011. (Updated 07/11/2011 — typo corrected.)
- Examples sheet 4, distributed on 15/11/2011.
- Examples sheet 5, final examples sheet.
Updated 02 Jan 2012