Ramsey theory refers to questions of the form "how many objects are needed to guarantee that a given property of the collection holds?"

A relatively simple example of a theorem from Ramsey theory is the Theorem on Friends and Strangers.

In any party of six people either at least three of them are (pairwise) mutual strangers or at least three of them are (pairwise) mutual acquaintances.

One goal of Ramsey theory is to calculate Ramsey numbers $R(r, s)$: For any positive integers $r$ and $s$, there is a smallest positive integer $R(r, s)$ such that any two-colouring of the edges of a complete graph on $R(r, s)$ vertices has a complete subgraph on $r$ which is entirely of the first colour, or a complete subgraph on $s$ vertices which is entirely of the second colour. The Theorem on Friends and Strangers shows that $R(3, 3) \leq 6$ (in fact, $R(3, 3) = 6$).

The notion of Ramsey numbers can be generalised by considering $k$-coloured graphs.

history | excerpt history