Ramsey's theorem

Named after British mathematician and philosopher Frank P. Ramsey.

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.

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

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

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