Extremal Combinatorics and its Methods

Winter 2019-2020

FU Berlin, Mathematics and Informatics



Course Details

Schedule

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.

Instructors

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
838-75217

Exams and Requirements

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

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.

Topics

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.

References

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

Prerequisites

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.

Exercises

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

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