Extremal Combinatorics and its Methods

Winter 2019-2020

FU Berlin, Mathematics and Informatics

Course Details


The lectures will be on Tuesdays and Thursdays from 12:30 to 14:00 in Arnimallee 6, SR 032 .

The exercise classes will be on Tuesdays from 14:15 to 16:00 in Arnimallee 6., SR 025/26 and Thursdays from 08:30 to 10:00 in Arnimallee 3, SR 024.

Office hours on request.


Tibor Szabó Michael Anastos
Arnimallee 3, Room 211a Arnimallee 3, Room 202
szabo at math dot fu-berlin dot de manastos at andrew dot cmu dot edu

Exams and Requirements

The final exam will take place on Thursday, February 20nd, 2020, from 9:00 to 12:00. (Results)

A make-up exam will be offered on Wednesday, April 1st, 2020, from 9:00 to 12:00

A full description of the formalities of the course and the requirements for successfully completing the course can be found here.


Over the course of this semester, we shall cover the following topics:

Extremal graph theory and the probabilistic method: Ramsey theory, Turán's theorem, the Regularity Lemma, Roth's Theorem, and selected topics.
Extremal combinatorics and the linear algebraic method: Sperner's Theorem, Kruskal-Katona, restricted intersections and applications, cap-sets and sunflowers.
Topological methods: Sperner's Lemma, independent transversals, and Kneser's conjecture.


Most of the course material can be found in the following books:
  • N. Alon and J. Spencer, The Probabilistic Method
  • L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics
  • R. Diestel, Graph Theory
  • J. Fox, Lecture notes
  • S. Jukna, Extremal Combinatorics
  • J. Matoušek, Using the Borsuk-Ulam Theorem
  • J. van Lint and R. Wilson, A Course in Combinatorics
  • D. West, Introduction to Graph Theory

For further reading, you are encouraged to consult either of the texts below:
  • B. Bollobás, Modern Graph Theory
  • L. Lovász, Combinatorial Problems and Exercises
  • J. Matoušek, Thirty-three Miniatures: Mathematical and Algorithmic Applications of Linear Algebra


Students should be familiar with basic graph theory and combinatorics (see the lecture notes of Discrete Math I, in particular its graph theory material), discrete probability, algebra and calculus.


Exercise sheets will be posted below every Tuesday, and should be submitted before 14:15 on Tuesday of the following week.

Assignment Due date Comments
Review sheet Not for submission some asymptotics
Sheet 1 22/10/2019
Sheet 2 29/10/2019
Sheet 3 05/11/2019 Footnote 2 corrected
Sheet 4 12/11/2019
Sheet 5 19/11/2019
Sheet 6 26/11/2019
Sheet 7 3/12/2019
Sheet 8 10/12/2019
Sheet 9 17/12/2019
Practice Exam 07/01/2020 Optional
Sheet 10 14/01/2020
Sheet 11 21/01/2020
Sheet 12 28/01/2020
Sheet 13 04/02/2020
Sheet 14
Sheet 15

Course Progress

As we make our way through the semester, we will provide below a brief review of the topics covered each week. Here you can find past lecture notes, which I hope to correct and revise as the semester goes along.

Week Topics References
Week 1 Ramsey theory: graphs, infinite version, small Ramsey numbers, multiple colours, lower bound Diestel, § 9.1
Alon-Spencer, § 1.1
Week 2 Ramsey theory: the Happy Ending Problem, hypergraphs, upper bounds Jukna § 4.10
Week 3 Improved upper bounds on hypergraph Ramsey numbers, Canonical Ramsey theorem, Two-colorability of Hypergraphs: initial upper and lower bounds
Week 4 Two-colorability: Random greedy colouring, Chromatic number and girth Alon Spencer § 1.3, Probabilistic Lens #3
Week 5 Turán theory: Erdős-Stone-Simonovits, Bipartite Turán problems, Kővári-Sós-Turán and Ks,t-free subgraphs
Week 6 Szemerédi Regularity Lemma (statement), Triangle Removal Lemma (proof), Regularity Lemma: Proof of Erdős-Stone theorem
Week 7 Introduction to k-AP free sets, Arithmetic progression free sets, Roth's theorem via regularity, Ramsey vs Turán, Van der Waerden's theorem
Week 8 Extremal Set Theory: Hypergraph Turán Problems, Intersecting Families, Sunflowers, Sperner's Theorem.
Week 9 Linear Algebra Method: Oddtown, Fisher's Inequality, L-intersecting sets Babai-Frankl §1.1
Week 10 Geometric Applications: Chromatic Number of Unit Distance Graphs, Borsuk's Conjecture.
Introduction to the Erdos-Szemerédi sunflower conjecture and the slide rank method
Babai-Frankl Chapter 4
Jukna §13.6
Week 11 The slice rank method, the cap-set problem, the Bollobás set-pairs inequality and graph saturation Babai-Frankl §5.6
Week 12 The Lovász set-pairs inequality and weak saturation, the Kruskal-Katona theorem Babai-Frankl §3.1 and 6.2, Jukna §10.4
Week 13 Kruskal-Katona Theorem, Sperner's Lemma Jukna §10.4
Fox, MAT307, Lecture 3
Week 14 Proof of Hall's Theorem via Sperner's Lemma, Independent transversals Aharoni,Haxell paper
Week 15 The Borsuk-Ulam theorem
Proof of Kneser's conjecture
The Ham-Sandwich Theorem