The following notes are from the Ramsey DocCourse in Prague 2016. The notes were taken and edited by myself and Michael Kompatscher. In the process we may have introduced some errors; email us or comment below and we will happily fix them.

**Title**: Bootcamp 1 – Informal meeting.

**Lecturer**: Jaroslav Nešetřil.

**Date**: September 20, 2016.

**Main Topics**: Overview over the topics of the DocCourse; classical result in Ramsey theory

**Definitions:** Arrow notation, Ramsey numbers, arithmetical progression

Bootcamp 1 – Bootcamp 2 – Bootcamp 3 – Bootcamp 4 – Bootcamp 5 – Bootcamp 6 – Bootcamp 7 – Bootcamp 8

## Introduction

The main scope of this lecture was to give a historical overview over classical results in Ramsey theory, including Ramsey’s theorem itself. Further the program of the DocCourse was presented, which can be found here.

## Main References

The three books below are a main references for Ramsey theory in general and the Bootcamp lectures in particular. Jarik also passed around an original version of Ramsey’s paper, which is depicted on the conference poster.

- Nešetřil, Rödl. “Mathematics of Ramsey theory”. 1990
- Graham, Rothschild. “Ramsey theory”. 1990
- Prömel. “Ramsey theory for discrete structures.”. 2013
- Ramsey. “On a Problem of Formal Logic.”. 1928

## Finite and infinite Ramsey theorem

In order to phrase Ramsey’s theorems we first introduce some standard notation:

**Definition**. We use the convention that for all integers . For a set and an integer , let us write for the set of all -element subsets of .

**Definition**. For we write

if for every partition of there exists an index and an with such that . In other words: for every coloring of with colors, there is a with , such that the coloring is is monochromatic on .

Then Ramsey’s theorem states as follows:

**The finite Ramsey theorem**. For all there is an such that

A proof of Ramsey’s theorem can be found in the notes to David Fox’ lectures (*Mike: Coming soon!*), including some estimates for the corresponding Ramsey numbers:

**Definition**. For given numbers we define the Ramsey number to be the minimal natural number , witnessing that .

By the pigeonhole principle we have . However already the situation for Ramsey number is much more complex, only estimates are known for .

Ramsey’s work did not result from pure interest in combinatorics, but was motivated by Hilbert’s Entscheidungsproblem, the problem of finding an algorithm that tells if every statement expressible in first-order logic is provable (from a given set of axioms). The finite Ramsey theorem was only used as an auxiliary result in “On a Problem of Formal Logic.”, in order to prove that every formula of the form

is decidable.

We remark that by Gödel’s incompleteness Theorem, the Entscheidungsproblem in general is not decidable; by a result of Trakthenbrot already adding one additional quantifier alternation results in undecidable formulas.

In the same paper Ramsey also presented a proof for the following infinite version of his theorem:

**The infinite Ramsey theorem**. For all

The proof of the infinite Ramsey theorem requires the axiom of choice. There exists a slight strengthening of the Finite Ramsey theorem, which we will denote by FRT*. In FRT*, we additionally can assume that the minimum monochromatic set is bounded by the size of :

**FRT* (Paris, Harrington, 1977)**. For there is an such that for every partition there exists an index and a -set such that and further holds.

We are going to show that the infinite Ramsey theorem implies the strengthened version of the finite Ramsey theorem:

**Proof**

Suppose that FRT* does not hold. Then there are such that there is a “bad partition” , i.e. a partition such that no -subset with lies entirely in one partition class. Note that restrictions of bad partitions of to , where is again a bad partitions.By compactness (König’s lemma), there is a sequence of bad partitions, which extend each other. Its limit gives us a partition . By the infinite Ramsey theorem there is an infinite set , such that is monochromatic; clearly then also every restriction of to is monochromatic. By choosing an such that we obtain a contradiction to the assumption that is a bad partition.

Note that, since the above proof of the FRT* uses the infinite Ramsey theorem, it requires also the axiom of choice. It can be shown that this assumption is indeed necessary: Paris and Harrington proved that FRT* is a true statement about the integers that could be stated in the language of arithmetic, but not proved in Peano arithmetic. It was already known that such statements existed by Gödel’s first incompleteness theorem, however no examples of “natural” such theorems were known.

Their proof lead also to the notion of indiscernibles in mathematical logic, i.e. are objects which cannot be distinguished by any property or relation defined by a formula.

## An historical overview

As mentioned above, Ramsey himself used his result only as an auxiliary result to prove statements about decidability. The Happy ending theorem is often considered as starting point for the development of Ramsey theory as a whole new branch of mathematics:

**Happy ending theorem (Erdős, Szemeredi 1935)**. such that, whenever are points in and no triple of points lies on a line, then there is a with such that is a convex polygon.

Ramsey’s theorem was preceded by several other results, which we nowadays consider to be part of Ramsey theory, although they were also not studied from a combinatorial point of view, when they were first proven. One example is Van der Waerden’s theorem:

**Van der Waerden’s theorem (1927)**. For all there is an such that for every partition there is an index , such contains an

**arithmetical progression**of length , i.e. a set of the form

,

where .

In reproving a theorem of Dickson on a modular version of Fermat’s conjecture, Schur showed the following:

**Schur’s theorem (1912)**. For all there is an such that for every partition there is an index and there are elements with .

Hilbert’s cube lemma is probably the earliest result which can be viewed as a Ramsey-type theorem (besides, of course, the pigeonhole principle). It was established in connection with investigations on the irreducibility of rational functions with integer coefficients.

**Hilbert’s cube lemma (1892)**. Let denote the power set of . Then Hilbert’s cube lemma states that for all there is an such that for every partition

,

there is an index and disjoints sets , such that every set of the form with lies in the partition class .