Ramsey theory, named after the British mathematician and philosopher

Frank P. Ramsey Frank Plumpton Ramsey (; 22 February 1903 – 19 January 1930) was a British philosopher, mathematician, and economist who made major contributions to all three fields before his death at the age of 26. He was a close friend of Ludwig Wittgenste ...

, is a branch of

mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a question of the form: "how big must some structure be to guarantee that a particular property holds?" More specifically, Ron Graham described Ramsey theory as a "branch of

combinatorics Combinatorics is an area of mathematics primarily concerned with counting, both as a means and an end in obtaining results, and certain properties of finite structures. It is closely related to many other areas of mathematics and has many appl ...

Examples

A typical result in Ramsey theory starts with some mathematical structure that is then cut into pieces. How big must the original structure be in order to ensure that at least one of the pieces has a given interesting property? This idea can be defined as partition regularity. For example, consider a

complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices is ...

of order ''n''; that is, there are ''n'' vertices and each vertex is connected to every other vertex by an edge. A complete graph of order 3 is called a triangle. Now colour each edge either red or blue. How large must ''n'' be in order to ensure that there is either a blue triangle or a red triangle? It turns out that the answer is 6. See the article on

Ramsey's theorem In combinatorics, Ramsey's theorem, in one of its graph-theoretic forms, states that one will find monochromatic cliques in any edge labelling (with colours) of a sufficiently large complete graph. To demonstrate the theorem for two colours (say ...

for a rigorous proof. Another way to express this result is as follows: at any party with at least six people, there are three people who are all either mutual acquaintances (each one knows the other two) or mutual strangers (none of them knows either of the other two). See

theorem on friends and strangers The theorem on friends and strangers is a mathematical theorem in an area of mathematics called Ramsey theory. Statement Suppose a party has six people. Consider any two of them. They might be meeting for the first time—in which case we will ...

. This also is a special case of Ramsey's theorem, which says that for any given integer ''c'', any given integers ''n''₁,...,''n''_''c'', there is a number, ''R''(''n''₁,...,''n''_''c''), such that if the edges of a complete graph of order ''R''(''n''₁,...,''n''_''c'') are coloured with ''c'' different colours, then for some ''i'' between 1 and ''c'', it must contain a complete subgraph of order ''n_i'' whose edges are all colour ''i''. The special case above has ''c'' = 2 and ''n''₁ = ''n''₂ = 3.

Results

Two key theorems of Ramsey theory are: *

Van der Waerden's theorem Van der Waerden's theorem is a theorem in the branch of mathematics called Ramsey theory. Van der Waerden's theorem states that for any given positive integers ''r'' and ''k'', there is some number ''N'' such that if the integers are colored, ea ...

: 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 An arithmetic progression or arithmetic sequence () is a sequence of numbers such that the difference between the consecutive terms is constant. For instance, the sequence 5, 7, 9, 11, 13, 15, . . . is an arithmetic progression with a common differ ...

of length ''n'' whose elements are all the same colour. *

Hales–Jewett theorem In mathematics, the Hales–Jewett theorem is a fundamental combinatorial result of Ramsey theory named after Alfred W. Hales and Robert I. Jewett, concerning the degree to which high-dimensional objects must necessarily exhibit some combinatorial ...

: For any given ''n'' and ''c'', there is a number ''H'' such that if the cells of an ''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: a multi-player ''n''-in-a-row

tic-tac-toe Tic-tac-toe (American English), noughts and crosses (Commonwealth English), or Xs and Os (Canadian or Irish English) is a paper-and-pencil game for two players who take turns marking the spaces in a three-by-three grid with ''X'' or ''O''. ...

cannot end in a draw, no matter how large ''n'' is, and no matter how many people are playing, if you play on a board with sufficiently many dimensions. The Hales–Jewett theorem implies

. A theorem similar to van der Waerden's theorem is ''

Schur's theorem In discrete mathematics, Schur's theorem is any of several theorems of the mathematician Issai Schur. In differential geometry, Schur's theorem is a theorem of Axel Schur. In functional analysis, Schur's theorem is often called Schur's property ...

'': 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 In mathematics, the Milliken–Taylor theorem in combinatorics is a generalization of both Ramsey's theorem and Hindman's theorem. It is named after Keith Milliken and Alan D. Taylor. Let \mathcal_f(\mathbb) denote the set of finite subsets of ...

. A classic reference for these and many other results in Ramsey theory is Graham, Rothschild, Spencer and Solymosi, updated and expanded in 2015 to its first new edition in 25 years. Results in Ramsey theory typically have two primary characteristics. Firstly, they are unconstructive: 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 In mathematics, the pigeonhole principle states that if items are put into containers, with , then at least one container must contain more than one item. For example, if one has three gloves (and none is ambidextrous/reversible), then there mu ...

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 Exponential may refer to any of several mathematical topics related to exponentiation, including: *Exponential function, also: **Matrix exponential, the matrix analogue to the above *Exponential decay, decrease at a rate proportional to value *Expo ...

, or even as fast as the Ackermann function are not uncommon. In some small niche cases, upper and lower bounds are improved, but not in general. 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 In computability theory, a primitive recursive function is roughly speaking a function that can be computed by a computer program whose loops are all "for" loops (that is, an upper bound of the number of iterations of every loop can be determined ...

function; see the

Paris–Harrington theorem In mathematical logic, the Paris–Harrington theorem states that a certain combinatorial principle in Ramsey theory, namely the strengthened finite Ramsey theorem, is true, but not provable in Peano arithmetic. This has been described by some (suc ...

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. Another large example is the

Boolean Pythagorean triples problem The Boolean Pythagorean triples problem is a problem from Ramsey theory about whether the positive integers can be colored red and blue so that no Pythagorean triples consist of all red or all blue members. The Boolean Pythagorean triples problem w ...

. Theorems in Ramsey theory are generally one of the following two types. Many such 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 its own structured object, but gives no information about which class this is. In other cases, the reason behind a ''Ramsey-type'' result is that the largest partition class always contains the desired substructure. The results of this latter kind are called either ''density results'' or ''Turán-type result'', after

Turán's theorem In graph theory, Turán's theorem bounds the number of edges that can be included in an undirected graph that does not have a complete subgraph of a given size. It is one of the central results of extremal graph theory, an area studying the large ...

. Notable examples include

Szemerédi's theorem In arithmetic combinatorics, Szemerédi's theorem is a result concerning arithmetic progressions in subsets of the integers. In 1936, Erdős and Turán conjectured that every set of integers ''A'' with positive natural density contains a ''k''-ter ...

, which is such a strengthening of van der Waerden's theorem, and the density version of the Hales-Jewett theorem..

Examples

Results

See also

References

Further reading