Course Details
Schedule
The lectures will be on Tuesdays and Wednesdays from 12:30 to 14:00 in Arnimallee 6, SR 032 .The exercise classes will be on Tuesdays from 16:15 to 18:00 in Takustr. 9, SR 049 and Wednesdays from 08:30 to 10:00 in Arnimallee 6, SR 032.
Office hours on request.
Please sign up for the announcements related to this course by entering your email address and name here.
Instructors
| Tibor Szabó | Anurag Bishnoi | ||
| Arnimallee 3, Room 211a | Arnimallee 3, Room 206 | ||
| szabo at math dot fu-berlin dot de | anurag.2357 at gmail dot com | ||
| 838-75217 |
Exams and Requirements
The final exam will take place on Wednesday, February 21st, 2018, from 9:00 to 12:00 in HFB/D auditorium (Garystr. 35-37). (Results)A make-up exam will be offered on Tuesday, April 10th, 2018, from 9:00 to 12:00 in A3/Hs 001 Auditorium (Arnimallee 3-5). (Results)
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
Some assorted notes:
Prerequisites
Students should be familiar with basic graph theory and combinatorics, discrete probability, algebra and calculus.Exercises
Exercise sheets will be posted below every Wednesday, and should be submitted before 16:15 on Tuesday of the following week.
| Assignment | Due date | Comments |
|---|---|---|
| Review sheet | Not for submission | some asymptotics |
| Sheet 1 | 24/10/2017 | R(3,4) |
| Sheet 2 | 07/11/2017 | |
| Sheet 3 | 14/11/2017 | Typos corrected |
| Sheet 4 | 21/11/2017 | |
| Sheet 5 | 28/11/2017 | |
| Sheet 6 | 05/12/2017 | Error in 1(a) corrected |
| Sheet 7 | 12/12/2017 | |
| Sheet 8 | 19/12/2017 | |
| Practice Exam | 09/01/2018 | Optionalsolutions |
| Sheet 9 | 16/01/2018 | |
| Sheet 10 | 23/01/2018 | |
| Sheet 11 | 30/01/2018 | |
| Sheet 12 | 6/02/2018 | |
| Sheet 13 | 13/02/2018 |
Course Progress
As we make our way through the semester, we will provide below a brief review of the topics covered each week.
| Week | Topics | References |
|---|---|---|
| Week 1 | Ramsey theory: graphs, infinite version, small Ramsey numbers, multiple colours, lower bound | Diestel, § 9.1 Alon-Spencer, § 1.1 lecture notes |
| Week 2 | Ramsey theory: the Happy Ending Problem, hypergraphs, upper bounds | Fox, MAT307, Lecture 6 Jukna § 4.10 lecture notes |
| Week 3 | Improved upper bounds on hypergraph Ramsey numbers | See lectures notes of Week 2 |
| Week 4 | Canonical Ramsey theorem, Two-colorability of Hypergraphs: initial upper and lower bounds | Alon Spencer § 1.3 lecture notes |
| Week 5 | Two-colorability: Random greedy colouring, Turán theory: Erdős-Stone-Simonovits, Bipartite Turán problems, Kővári-Sós-Turán and Ks,t-free subgraphs | Pluhár Cherkashin-KozikNotes on Turánlecture notes |
| Week 6 | Chromatic number and girth, Szemerédi Regularity Lemma (statement), Triangle Removal Lemma (proof) | Alon-Spencer, Probabilistic Lens #3 lecture notes Alon-Spencer §17.3 |
| Week 7 | Regularity Lemma: Proof of Erdős-Stone theorem, Introduction to k-AP free sets | Diestel, §7.4 and 7.5 lecture notes |
| Week 8 | Arithmetic progression free sets, Roth's theorem via regularity, Ramsey vs Turán, Van der Waerden's theorem | slide 1, slide 2 lecture notes |
| Week 9 | Extremal Set Theory: Hypergraph Turán Problems, Intersecting Families, Sunflowers, Sperner's Theorem. Linear Algebra Method: Oddtown and Fisher's Inequality | Babai-Frankl §1.1 lecture notes |
| Week 10 | Proof of Fisher's Inequality, L-intersecting sets, Geometric Applications: Chromatic Number of Unit Distance Graphs, Borsuk's Conjecture | Babai-Frankl Chapter 4 Jukna §13.6 lecture notes |
| Week 11 | Proof of Borsuk's conjecture, Erdos-Szemerédi sunflower conjecture and the slice rank method | Babai-Frankl §5.6 Kahn-Kalai Naslund-Sawin Notes by Frank De Zeeuw |
| Week 12 | The cap-set problem LYM inequality and Bollobás's Theorem | Ellenberg-GijswijtTao's blogpost lecture notes |
| Week 13 | The Bollobás set-pairs inequality and graph saturation, Weak saturation and the skew Bollobás set-pairs inequality, The Kruskal-Katona theorem: statement | Babai-Frankl §3.1 and 6.2, Jukna §10.4 lecture notes |
| Week 14 | Kruskal-Katona Theorem, Sperner's Lemma | Jukna §10.4 Fox, MAT307, Lecture 3 lecture notes |
| Week 15 | Independent Transversals, Fair Division and Simmons-Su Protocol | Szabó-TardosSu lecture notes |
| Week 16 | The Borsuk-Ulam theorem Proof of Kneser's conjecture The Crossing Number Inequality and Unit Distances |
Matoušek, §2.1 and 3.3 lecture notes |