ScheduleThe 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 RequirementsThe 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.
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.
ReferencesMost 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
PrerequisitesStudents 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.
|Review sheet||Not for submission||some asymptotics|
|Sheet 3||05/11/2019||Footnote 2 corrected|
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 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|