## 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 K_{s,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 |