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
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.
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:
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:
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:
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
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 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 :
We are going to show that the infinite Ramsey theorem implies the strengthened version of the finite Ramsey theorem:
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:
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:
In reproving a theorem of Dickson on a modular version of Fermat’s conjecture, Schur showed the following:
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.
there is an index and disjoints sets , such that every set of the form with lies in the partition class .