Course info

Prerequisites

Mathematical maturity consistent with having done a first degree in mathematics. Students need to be able to write mathematical proofs and are expected to have done courses that cover basic probability, discrete mathematics, analysis and (linear) algebra. In particular, we will use random variables, expectation, variance, binomial distribution, vector spaces, polynomials, matrix rank, inner products, finite fields, groups, binomial coefficients and graphs.

If a student wishes to brush up on the prerequisites, lecture notes and exercises are available via https://courses.maths.ox.ac.uk/.

• Required: all ‘pure’ first-year courses: M1: Linear Algebra I, M1: Linear Algebra II, M1: Groups and Group Actions, M2: Analysis I - Sequences and Series, M2: Analysis II - Continuity and Differentiability, M2: Analysis III - Integration, M3: Probability.
• Helpful to have seen some for broader understanding: ASO: Graph Theory, A0: Linear Algebra, A2: Metric Spaces and Complex Analysis, A3: Rings and Modules, A4: Integration, A5: Topology, A8: Probability, B4.1 Functional Analysis I, B8.5 Graph Theory

Aim of the course

This course covers selected topics and techniques in Ramsey theory, extremal set theory, random graphs, structural and extremal graph theory. Central to the course are applications of the “probabilistic method”, a method that was championed by Erd˝os in the twentieth century, and by now has become standard in the modern mathematical repertoire. The principle is simple: to guarantee the existence of an object with some desired properties, it suffices to set up a probability space over the objects and show there’s a chance the property holds. In spite of its simple and tautological nature, this has proven surprisingly powerful and versatile, with impact spanning mathematics, computer science, engineering, and networks, yielding many results that seemingly have nothing to do with probability. We focus on results in combinatorics, covering Ramsey’s theorem, Tur´an’s theorem, the Bollob´as–Thomason threshold theorem, Dilworth’s theorem, the Erd˝os–Ko–Rado theorem, and Szemer´edi’s regularity lemma. Although combinatorics has long been associated with a “problem-solving” style of mathematics, in this course we thread through underlying ideas and intuition, especially the link between combinatorics and algorithms, appearance of phase transitions, and relationship between local and global structure

Rules about Homework/Exam

Bi-weekly homework exercises count for 30% of the grade and a written final exam counts for 70% of the grade, though we only count the homework score if it is higher than the exam score. The exam grade needs to be at least 5.0 to pass the course.

For the retake, the homework score does not count as part of the grade. The retake is intended as a written exam, but we reserve the possibility to administer it as an oral exam depending on the number of students registered (this becomes clear shortly after the results of the final exam are known).

Lecture Notes/Literature

Lecture notes issued by the lecturers.

Additional resources:

• Noga Alon and Joel Spencer. The Probabilistic Method (4th ed.).
• Vaˇsek Chv´atal. The Discrete Mathematical Charms of Paul Erd˝os.
• Stasys Jukna. Extremal Combinatorics: With Applications in Computer Science.

Lecturers Carla Groenland (TU Delft) and Ross Kang (UvA)