## 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:00A 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 |

## 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 |