Bootcamp 1 – Ramsey DocCourse Prague 2016 – Mike Pawliuk

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 $n = \{0,1,\ldots, n-1\}$ for all integers $n$ . For a set $Y$ and an integer $p$ , let us write $\binom{Y}{p}$ for the set of all $p$ -element subsets of $Y$ .

Definition. For $k,p,n,N \in \mathbb N$ we write
$\displaystyle N \longrightarrow (n)_k^p$
if for every partition $\mathcal A_1 \cup \cdots \mathcal A_k$ of $\binom{N}{p}$ there exists an index $i_0$ and an $Y \subset N$ with $|Y| = n$ such that $\binom{Y}{p} \subseteq \mathcal A_i$ . In other words: for every coloring of $\binom{N}{p}$ with $k$ colors, there is a $Y$ with $|Y|=n$ , such that the coloring is is monochromatic on $\binom{Y}{p}$ .

Then Ramsey’s theorem states as follows:

The finite Ramsey theorem. For all $k,p,n \in \mathbb N$ there is an $N \in \mathbb N$ such that $N \longrightarrow (n)_k^p$

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 $k,p,n$ we define the Ramsey number $r(p,k,n)$ to be the minimal natural number $N$ , witnessing that $N \longrightarrow (n)_k^p$ .

By the pigeonhole principle we have $r(1,k,n) = k(n-1) + 1$ . However already the situation for Ramsey number $r(2,2,n)$ is much more complex, only estimates are known for $n \geq 5$ .

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

$\displaystyle \exists x_1 \exists x_2 \cdots \exists x_n \forall y_1 \forall y_2 \cdots \forall y_n \phi(x_1, \ldots, x_n, y_1, \ldots, y_n)$
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 $k,p \in \mathbb N: \omega \longrightarrow (\omega)_k^p$

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 $Y$ is bounded by the size of $Y$ :

FRT* (Paris, Harrington, 1977). For $k,p,n \in \mathbb N$ there is an $N \in \mathbb N$ such that for every partition $\binom{N}{p} = \mathcal A_1 \cup \cdots \cup \mathcal A_k$ there exists an index $i_0$ and a $n$ -set $Y$ such that $\binom{Y}{p} \subset \mathcal A_{i_0}$ and further $|Y| \geq \min(Y)$ 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 $k,p,n \in \mathbb N$ such that $\forall N \in \mathbb N$ there is a “bad partition” $\binom{N}{p} = \mathcal A_1^N \cup \cdots \mathcal A_{k}^N$ , i.e. a partition such that no $n$ -subset $Y$ with $\min(Y) \leq n$ lies entirely in one partition class. Note that restrictions of bad partitions of $\binom{N}{p}$ to $\binom{M}{p}$ , where $M \leq N$ 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 $\binom{\omega}{p} = \mathcal A_1 \cup \cdots \mathcal A_{k}$ . By the infinite Ramsey theorem there is an infinite set $Y \subset \omega$ , such that $\binom{Y}{p}$ is monochromatic; clearly then also every restriction of $\binom{Y}{p}$ to $\binomial{N}{p}$ is monochromatic. By choosing an $N$ such that $N \cap Y \geq \min(Y)$ we obtain a contradiction to the assumption that $\binom{N}{p} = \mathcal A_1^N \cup \cdots \mathcal A_{k}^N$ 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). $\forall n \exists N$ such that, whenever $\{x_1,\ldots,x_N\}$ are points in $\mathbb R^2$ and no triple of points lies on a line, then there is a $Y \subset X$ with $|Y| \geq n$ such that $Y$ 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 $k,n \in \mathbb N$ there is an $N \in \mathbb N$ such that for every partition $N = \mathcal A_1 \cup \cdots \cup \mathcal A_k$ there is an index $i_0$ , such $\mathcal A_{i_0}$ contains an arithmetical progression of length $n$ , i.e. a set of the form

$\displaystyle \{ a_0, a_0 + d, a_0 +2d, \ldots, a_0 + (n-1)d \}$
,
where $a_0, d \in \mathbb N$ .

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

Schur’s theorem (1912). For all $k \in \mathbb N$ there is an $N \in \mathbb N$ such that for every partition $N = \mathcal A_1 \cup \cdots \cup \mathcal A_k$ there is an index $i_0$ and there are elements $\{x,y,z\} \subset \mathcal A_{i_0}$ with $x +y = z$ .

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 $\mathcal P(N)$ denote the power set of $N = \{0,1,\ldots,n-1\}$ . Then Hilbert’s cube lemma states that for all $k,n \in \mathbb N$ there is an $N$ such that for every partition

$\displaystyle \mathcal P(N) = \mathcal A_1 \cup \cdots \cup \mathcal A_k$
,
there is an index $i_0$ and disjoints sets $A_0,A_1,\ldots, A_n \subseteq N$ , such that every set of the form $A_0 \cup \bigcup_{j \in J}A_j$ with $J \subseteq \{1,\ldots, n\}$ lies in the partition class $\mathcal A_{i_0}$ .

Introduction

Main References

Finite and infinite Ramsey theorem

An historical overview

Share this:

Like this:

Related

Leave a Reply Cancel reply