1.3: Ramsey Theory

Last updated
Save as PDF

Page ID: 70854

Joy Morris
University of Lethbridge

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

Ramsey theory takes its name from Frank P. Ramsey, a British mathematician who died in 1930 at the tragically young age of 26, when he developed jaundice after an operation.

Ramsey was a logician. A result that he considered a minor lemma in one of his logic papers now bears the name “Ramsey’s Theorem” and was the basis for this branch of mathematics. Its statement requires a bit of graph theory: given \(c\) colours and fixed sizes \(n_1, . . . , n_c\), there is an integer \(r = R(n_1, . . . , n_c)\) such that for any colouring the edges of a complete graph on r vertices, there must be some \(i\) between \(1\) and \(c\) such that there is a complete subgraph on \(n_i\) vertices, all of whose edges are coloured with colour \(i\).

In addition to requiring some graph theory, that statement was a bit technical. In much less precise terms that don’t require so much background knowledge (but could be misleading in specific situations), Ramsey Theory asserts that if structure is big enough and contains a property we are interested in, then no matter how we cut it into pieces, at least one of the pieces should also have that property. One major theorem in Ramsey Theory is van der Waerden’s Theorem, which states that for any two constants \(c\) and \(n\), there is a constant \(V(c, n)\) such that if we take \(V(c, n)\) consecutive numbers and colour them with \(c\) colours, there must be an arithmetic progression of length \(n\) all of whose members have been coloured with the same colour.

Example \(\PageIndex{1}\)

Here is a small example of van der Waerden’s Theorem. With two colours and a desired length of 3 for the arithmetic progression, we can show that \(V (2, 3) > 8\) using the following colouring:

3 4 5 6 7 8 9 10

(In case it is difficult to see, we point out that 3, 4, 7, and 8 are black, while 5, 6, 9, and 10 are grey, a different colour.) Notice that with eight consecutive integers, the difference in a three-term arithmetic progression cannot be larger than three. For every three-term arithmetic progression with difference of one, two, or three, it is straightforward to check that the numbers have not all received the same colour.

In fact, \(V (2, 3) = 9\), but proving this requires exhaustive testing.

We will touch lightly on Ramsey Theory in this course, specifically on Ramsey’s Theorem itself, in the context of graph theory.