Probabilistic and Extremal Combinatorics - M1 - 8EC

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 Thomassen's theorem. 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.

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