UU logo

Master course:
Probabilistic and extremal combinatorics

Fall 2016

Brief overview of the course

We will cover selected topics in discrete geometry, additive number theory, Ramsey theory, extremal set theory, and random and extremal graph theory. This includes some of the most attractive results in modern mathematics such as Szemerédi's theorem (on arithmetic progressions in integer subsets of positive density), the Hales-Jewett theorem, bounds on the size of sum-free sets, Kahn and Kalai's counterexample to Borsuk's conjecture (on dissecting sets in d-dimensional space into pieces of strictly smaller diameter) and bounds on the Hadwiger-Nelson problem (of colouring d-dimensional space such that points at distance one receive different colors).
Central to the course are applications of "the probabilistic method", popularized by Pál Erdős in the second half of the twentieth century. That is, we use probabilistic reasoning to obtain (often extremely elegant and short) proofs of statements that seemingly have nothing to do with probability. We will also cover the use of some other methods, including algebraic ones. More specifically, the tools we will cover include the Lovász local lemma, Alon's Nullstellensatz, Szemerédi's regularity lemma, the basic first and second moment methods, Martingale and other concentration inequalities.

Time and location

The course takes place on Fridays 10:00 - 12:45 at the UvA campus in Amsterdam, in room SP C1.112.
The first lecture is in week 38, on Friday 23 September 2013.

Lecturers

Ross J. Kang and Tobias Müller will each present roughly half of the lectures.

Examination

Homework exercises and a written examination (re-examination as oral exam). Homework counts for 40% of the final grade.
A list of examinable topics is available.

We also have available:

Note that there are some minor differences between the material covered this year and in previous years. Also, the solutions we provide do not always correspond to how the answers should have been written on the exam to get full marks.

The exam of 13 January 2017 and the solutions are now available.

Literature

Weekly schedule