Lecture 12*: Introduction to Ramsey theory
- Some exemplary problems
the party problem, Schur's theorem, points in convex position
- Ramsey theorem
proof of the infinite version, compactness argument to the finite version, fine bounds for special cases
- Hales-Jewett theorem
why high-dimensional tic-tac-toe game cannot end in a draw, formal formulation, van der Waerden's theorem
Informally saying, Ramsey theory is a theory of numerous results in different areas of discrete mathematics, all basically showing that "a complete disorder is mathematically impossible". In other words, Ramsey theory is looking for order inside disorder. We very briefly introduce some fundamental directions of research of this interesting branch of mathematics. This lecture stands somehow aside of the rest of the whole subject, but is neverthless very interesting from theoretical point of view.
Generally, the additional topics are not covered at all by the course textbook, and only online materials are presented.