MTH711U: Extremal Combinatorics, Autumn 2011

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

Materials

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.