Extremal Combinatorics and its Methods

Winter 2017-2018

FU Berlin, Mathematics and Informatics



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 Optional
solutions
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-Kozik
Notes on Turán
lecture 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-Gijswijt
Tao'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ó-Tardos
Su
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