Ramsey's theorem

English

Etymology

Named after British mathematician and philosopher Frank P. Ramsey.

Noun

Ramsey's theorem (countable and uncountable, plural Ramsey's theorems)

1. (mathematics) A (version of a) theorem concerning the existence of cliques in a labelled complete graph.
   1. The theorem that any graph labelling (with colours) of a sufficiently large complete graph contains monochromatic cliques.
   2. The theorem that any graph labelling (with colours) of an infinite complete graph contains at least one infinite monochromatic clique.

Usage notes

Equivalent statements exist for other mathematical contexts. For instance, for a combinatoric statement of the infinitary version: If $A_{1}\cup A_{2}\cup \dots \cup A_{n}=\mathbb {N} ^{2}$ is a partition of $\mathbb {N} ^{2}$, then there exists an infinite subset $X\subseteq \mathbb {N}$ that is homogeneous for the partition (i.e., for some $i,X^{2}\subseteq A_{i}$).

Synonyms

• (finite version of theorem): finite Ramsey's theorem
• (infinite version of theorem): infinite Ramsey's theorem

Further reading

• Infinitary combinatorics on Wikipedia.Wikipedia
• Ramsey theory on Wikipedia.Wikipedia
• Van der Waerden number on Wikipedia.Wikipedia