MA010 Graph Theory (an online guide)

Lecture 12*: Introduction to Ramsey theory

Outline

  • 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

Goals

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.

 

[BOOK]Generally, the additional topics are not covered at all by the course textbook, and only online materials are presented.

Alternative book: [Ramsey Theory, In: Handbook of combinatorics (vol. 2)]
                                                      [Ramsey theory, by Graham, Rothschild, Spencer]

Následující