Ramsey Theory - Results

Results

Two key theorems of Ramsey theory are:

• Van der Waerden's theorem: For any given c and n, there is a number V, such that if V consecutive numbers are coloured with c different colours, then it must contain an arithmetic progression of length n whose elements are all the same colour.

• Hales-Jewett theorem: For any given n and c, there is a number H such that if the cells of a H-dimensional n×n×n×...×n cube are coloured with c colours, there must be one row, column, etc. of length n all of whose cells are the same colour. That is, if you play on a board with sufficiently many dimensions, then multi-player n-in-a-row tic-tac-toe cannot end in a draw, no matter how large n is, and no matter how many people are playing. Hales-Jewett theorem implies Van der Waerden's theorem.

A theorem similar to van der Waerden's theorem is Schur's theorem: for any given c there is a number N such that if the numbers 1, 2, ..., N are coloured with c different colours, then there must be a pair of integers x, y such that x, y, and x+y are all the same colour. Many generalizations of this theorem exist, including Rado's Theorem, Rado-Folkman-Sanders theorem, Hindman's theorem, and the Milliken-Taylor theorem. A classic reference for these and many other results in Ramsey theory is Graham, Rothschild and Spencer.

Results in Ramsey theory typically have two primary characteristics. Firstly, they are non-constructive: they may show that some structure exists, but they give no process for finding this structure (other than brute force search). For instance, the pigeonhole principle is of this form. Secondly, while Ramsey theory results do say that sufficiently large objects must necessarily contain a given structure, often the proof of these results requires these objects to be enormously large – bounds that grow exponentially, or even as fast as the Ackermann function are not uncommon. In many cases these bounds are artifacts of the proof, and it is not known whether they can be substantially improved. In other cases it is known that any bound must be extraordinarily large, sometimes even greater than any primitive recursive function; see the Paris-Harrington theorem for an example. Graham's number, one of the largest numbers ever used in serious mathematical proof, is an upper bound for a problem related to Ramsey theory.

Theorems in Ramsey theory are generally one of the two types. Many theorems, which are modeled after Ramsey's theorem itself, assert that in every partition of a large structured object, one of the classes necessarily contains a large structured subobject, but give no information about which class this is. Occasionally, the reason behind such Ramsey-type results is that the largest partition class always contains the desired substructure. The results of this kind are called either density results or Turán-type result, after Turán's theorem. Notable examples include Szemerédi's theorem, which is such a strengthening of van der Waerden's theorem, and the density version of Hales-Jewett theorem.