Ramsey theory (ETH Zürich, spring 2024)

Lecture notes (last updated 13/12/2024)

Syllabus

Feb 21: Introduction, classical bounds on Ramsey numbers
Feb 28: Lower bounds on multicolor Ramsey numbers
Mar 6: Off-diagonal Ramsey numbers—upper bounds
Mar 13: Off-diagonal Ramsey numbers—lower bounds
Mar 20: Graph Ramsey numbers—trees, complete bipartite graphs, sparse graphs
Mar 27: Ramsey numbers of sparse graphs and the regularity method in Ramsey theory
Apr 3: no lecture (Easter holiday)
Apr 10: Restricted Ramsey graphs and the induced Ramsey theorem
Apr 17: The Erdős–Szemerédi multicolor problem and the structure of C-Ramsey graphs
Apr 24: The Hales–Jewett theorem: statement and applications
May 1: no lecture (Labour day)
May 8: The Hales–Jewett theorem: more applications and proof
May 15: Hypergraph Ramsey numbers—stepping up and stepping down
May 22: Points in convex position, monotone subsequences, and the canonical Ramsey theorem
May 29: The book algorithm

Homework

All homework is optional, so there are far more problems per homework than I expect a student to solve in a week. Try your hand at the problems that seem the most interesting!

Homework 1, released February 19
Homework 2, released February 27
Homework 3, released March 6
Homework 4, released March 13
Homework 5, released March 19
Homework 6, released March 26
Homework 7, released April 9
Homework 8, released April 17
Homework 9, released April 23
Homework 10, released May 8
Homework 11, released May 15
Homework 12, released May 21

Solutions to selected exercises — send me an email if you would like a solution to a certain problem!

Practice Exam

The practice exam is here. Like the real exam, it has six problems and is meant to be solved in 3 hours.

Solutions to the practice exam are here.

Exam solutions

The exam for the course took place on August 30. Solutions to the exam can be found here.