UU logo

Master course:
Probabilistic and extremal combinatorics

Fall 2013

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 Tuesdays 14:00 - 16:45 at the VU campus in Amsterdam.
The first lecture is in week 38, on Tuesday 17 September 2013.

The location of the lectures is as follows. Week 38: HG-01A05, weeks 39, 40: WN-M655, week 41-43: HG-04A04, week 44: WN-M143, week 45-48: WN-M623, week 49, 50: WN-F647. (HG = "hoofdgebouw", WN = "W & N gebouw")

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 50% of the final grade.

The exam will took place on 10 December 2013, 14:00-16:30, room WN-F647.

List of examinable topics

Statement and proof: Erdos-Ko-Rado theorem; Frankl-Wilson theorem; Exponential lower bound on chromatic number of d-space; Counterexample to Borsuk's conjecture; Sperner's theorem; Turan's theorem; Erdos-Stone theorem; crossing number inequality; Erdos-Szekeres upper bound recurrence and Erdos probabilistic lower bound for 2-colour graph Ramsey numbers; Schur's theorem assuming graph Ramsey's theorem; Erdos' construction of graphs with arbitrarily high girth and chromatic number; Diananda and Yap upper bound for sum-free sets in finite groups assuming Kneser's theorem; Erdos' construction of large sum-free sets of integers; Van der Waerden's theorem assuming Hales-Jewett theorem; Triangle removal lemma assuming Szemeredi's regularity lemma; Roth's theorem assuming triangle removal lemma.
Theorem statements only: Ramsey's theorem, full form (multicolour and hypergraphs); Goodman's formula; Erdos and Rado upper bound; Kneser's theorem; Hales-Jewett theorem and density version; Szemeredi's theorem; Szemeredi's regularity lemma.

Practice Exam

For your convenience we have made a practice exam. You can find it here. Solutions can be found here.

The real exam

The written exam can be found here, and solutions can be found here.

Literature

Weekly schedule