Probabilistic and Extremal Combinatorics [Fall 2019]
Prerequisites
Basic knowledge of probability and (linear) algebra. For probability: chapters 1-5, 7, 8 of "Elementary Probability" (2nd edition) by Stirzaker. For algebra: chapter I of "algebra"by Hungerford all of "linear algebra" by Serge Lang.
Some mathematical maturity consistent with having done a first degree in Mathematics.
Aim of the course
Central to this course are applications of the “probabilistic method”, championed by Pál Erdős in the second half of the twentieth century.
That is, the use of probabilistic reasoning to obtain (often very elegant and surprisingly short) proofs of statements that seemingly have little to do with probability. This has proven to be an extremely powerful idea that has had a major impact on combinatorial mathematics over the past seventy years, and continues to be applied with great success.
The course covers 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).
Through the presentation of these topics/results, we illustrate the broad application of more general purpose tools such as the Lovász local lemma, Szemerédi's regularity lemma, the linear algebra method, the first and second moment methods, martingale and other concentration inequalities.
Lecturers
T. Müller (UU) & R. Kang (RU)