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. (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.
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 | |
| 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 Solutions |
| 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 |