Exams
1st Exam: February 27th 2024, 10:00 - 13:00, A6/SR032
2nd Exam: April 9th 2024, 10:00 - 13:00, A6/SR032
- You are allowed to take both exams. If you take both, the better grade will be your final course grade.
- If you want to take the first exam, please register for the exam on Whiteboard until February 26.
- Be aware that you are allowed to bring a cheat sheet to the exam.
- one side of an A4 paper, handwritten, with your name on it
- For Part A of the exam, you have to give us the cheat sheet. At any time during the exam, you can signal us to get your cheat sheet back but at this point, you have to submit all your solutions for part A.
- Please do not forget to bring your personal ID and your student ID.
- Furthermore, you have to bring a pen. Paper will be provided by us.
Content
Extremal Combinatorics investigates how large/how small can a collection of finite objects be if it satisfies certain properties. The underlying set could be equiped with some structure (such as the set of integers, the Euclidean plane, or a vector space) or have none (and simply host a graph or hypergraph). The desired properties can also vary greatly; many fundamental problems can be formulated in this framework and are often related to other areas including Computer Science, Information Theory, Number Theory, and Geometry. In this course we cover the classics as well as some important new developments. Besides the standard combinatorial tools we give particular emphasis to the systematic study of various methods that arose from other branches of mathematics. Topics include:
- Struture and randomness in combinatorics: Ramsey- and Turán-theory, Szemerédi's Regularity Lemma, Roth's Theorem, independent sets and colorings.
- Extremal combinatorics and the linear algebra method: Sperner's Theorem, Kruskal-Katona Theorem, restricted intersections and their applications, sunflowers and cap-sets.
- Topological methods: Sperner's Lemma, independent transversals, and Kneser's conjecture.
Week 2: Probabilistic method with alteration, Van der Waerden's Theorem, Happy Ending Problem.
Week 3: Hypergraph Ramsey Theorem (two proofs for two colors), Infinite Ramsey Theorem, Canonical Ramsey Theorem for graphs
Week 4: Property B (evolving proofs)
Week 5: Graphs with high chromatic number and girth. Mantel's Theorem, Turán's Theorem (several proofs, tightness)
Week 6: Turán number, Erdős-Stone Theorem and the Erdős-Simonovits Corollary, Turán number of the four-cycle
Week 7: Turán density, hypergraph Turán problems, supersaturation, KST-Theorem, Hypergraph KST
Week 8: No short even cycles, Dependent random choice, regular pair/partition
Week 9: Szemerédi Regularity Lemma, Triangle Removal Lemma, Property Testing
Week 10: Proof of Szemerédis Regularity Lemma
Week 11: Roth’s Theorem, Behrend’s Construction, Ramsey-Turán-type problem
Week12: Sperner’s Theorem, Erdős-Ko-Rado for intersecting families, Erdős-Rado for sunflowers, Erdős-de Brujin for {1}-intersecting families, Non-uniform Fisher inequality
Week 13: The phase transition in the Erdős-Rényi random graph model, subcritical and supercritical regime
Week 14: Long paths and cycles in random graphs, DFS algorithm, Percolation of the hypercube
Week 15: Eventown, Oddtown, Frankl-Wilson Theorem
Week 16: Ray-Chaudhuri-Wilson Theorem, Slice rank Lemma, Erdős-Szemerédi Conjecture for l = 3, Capset Theorem of Ellenberg and Gijswijt
Prerequisites
Bachelor level Analysis, Linear Algebra, Probability, and an introductory course in Combinatorics and Graph Theory (for example, Discrete Mathematics I). In particular some familiarity with the following topics/concepts will be necessary:
- Elementary counting and proof techniques (pigeonhole principle, double counting), asymptotic notation (O, o, Ω, ω)
- Basic Graph Theory (connectivity, matchings, bipartite graphs, planarity, chromatic number, independence number, Hall’s Theorem, Ramsey’s Theorem)
Credits
Students interested in the algorithmic aspects of Discrete Mathematics are encouraged to take the Discrete Mathematics II-Optimization course offered by Ralf Borndörfer.
It is possible to take both courses (Optimization and Extremal Combinatorics) within the FU Master curriculum: one of them can be designated the Discrete Mathematics II modul, the other one an Ergänzungsmodul Ausgewählte Themen A, B, or C.
Homework and Aktive Teilnahme
Each Friday, we will publish an Exercise Sheet. You have to prepare solutions in groups of 2 and upload them on Whiteboard. To get the "Aktive Teilnahme" of the course, you have to score at least 60% of the points of the exercise sheets.
If you have trouble finding a homework partner, you can post something in the forum. Probably there are still some other students who are looking for a partner.
What should I do if I am not in Berlin yet?
You should try to be in Berlin during the whole term since the lectures and exercise classes are in-person only. However, if you can't make it at the beginning of term, you can try to attend the course remotely. Preferably, you find a partner who is in Berlin and can send you the notes of the lectures and exercise classes. It is important that you start working on the exercise sheets from the very beginning, so you won't have any trouble getting the "Aktive Teilnahme".
For the final exam at the end of the term, you have to be in Berlin.
Contact
- Lectures: Prof. Dr. Tibor Szabó: (szabo@zedat.fu-berlin.de), Dr. Olaf Parczyk (parczyk@mi.fu-berlin.de)
- Homeworks and Exercise Classes: Silas Rathke (s.rathke@fu-berlin.de)
Literatur
The material is selected from several textbooks:
N. Alon and J. Spencer, The Probabilistic Method
L. Babai and P. Frankl, Linear Algebra Methods in Combinatorics
R. Diestel, Graph Theory
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
Y. Zhao, Graph Theory and Additive Combinatorics