Extremal Combinatorics, Autumn 2012
In extremal combinatorics, one (mostly) studies questions of the following form: how large (or small) can various parameters associated with combinatorial objects be?
For example, how many edges can a graph on n vertices have if it does not contain a triangle? What is the maximum number of subsets that you can pick from an n-element set if no set is allowed to contain another? This module will cover a number of central results of this flavour for both graphs and set systems. 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 from 12 pm – 2 pm in room 103 (maths). See the mathematics timetable.
- Tutorials: Tuesdays 9 am – 10 am in room 103 (maths).
- Lecturer: Eoin Long, room 503 (maths).
Please feel free to contact me if you would like to talk about anything to do with the course; E.P.Long [at] qmul [dot] ac [dot] uk.
While complete notes will be provided in lectures, you may also find the following texts helpful:
- Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability, by B. Bollobás, CUP, 1986.
- Modern Graph Theory , by B. Bollobás, Springer, 1998.
- Graph Theory , by R. Diestel, Springer, 2010. A free electronic version of this book is available here.
- Extremal Combinatorics: With Applications in Computer Science, by S. Jukna, Springer, 2001.
Notes from a previous version of this course, given by Professor Keevash, are available here.