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:

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.

Example Sheets:

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

  1. Example sheet 1, 28/09/2012.
  2. Example sheet 2, 16/10/2012.
  3. Example sheet 3, 13/11/2012.
  4. Example sheet 4, 4/12/2012.

Suggested reading:

While complete notes will be provided in lectures, you may also find the following texts helpful:

  1. Combinatorics: Set Systems, Hypergraphs, Families of Vectors, and Combinatorial Probability, by B. Bollobás, CUP, 1986.
  2. Modern Graph Theory , by B. Bollobás, Springer, 1998.
  3. Graph Theory , by R. Diestel, Springer, 2010. A free electronic version of this book is available here.
  4. 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.