Introduction to Ramsey Theory: Students' Projects

Subsection 14.8.1 Daniel Král's favourite Ramsey theory statement.

Dr. Král's favourite Ramsey theory statement is the Canonical Ramsey Theorem, due to Erdős and Rado. [14.8.3.5]

This is from Dr. Král's message to us:

Suppose that you colour \(k\)–tuples of integers (with as many or as few colours as you like). Clearly, one cannot ask that in each colouring there is an infinite set such that all its \(k\)–tuples are monochromatic, as if each \(k\)–tuple can get a different colour.

So, one needs to permit as an outcome that all \(k\)–tuples have different colours.

Suppose that to each \(k\)–tuple a colour is assigned based on the smallest element, i.e., a \(l\)–tuple \(a_1\lt \cdots \lt a_k\) is coloured by \(a_1\text{.}\) So, we need to permit this outcome as well.

The statement of the theorem uses the following notion. for a set \(R\text{,}\) a subset of \(\{1,\ldots,k\}\text{,}\) we say that a colouring of \(k\)–tuples is \(R\)–canonical if two \(k\)–tuples \(a_1\lt \cdots \lt a_k\) and \(b_1\lt \cdots \lt b_k\) have the same colour if and only if \(a_i=b_i\) for all \(i\) in \(R\text{.}\) [14.8.3.3]

Theorem 14.8.1. The Canonical Ramsey Theorem.

Any colouring of integers has an infinite subset such that the restriction of the colouring to the \(k\)–tuples formed by elements of this subset is \(R\)–canonical for some \(R\text{.}\)

Note that If \(R\) is the empty set, then all \(k\)–tuples have the same colour and if \(R=\{1,\cdots,k\}\text{,}\) then all \(k\)–tuples have different colours. [14.8.3.3]

Subsection 14.8.2 Reflection

As we are undergraduate students studying both computing science and mathematics ourselves, we were thrilled to be able to communicate with and learn form such an established mathematician and computer scientist.