Proposed by Toby Walsh

The Ramsey number R(k,l) is the smallest number such that every graph with this or more nodes either contains a clique of size k or an independent set of size l. Ramsey proved that such such a number exists for every (k,l) pair, but computing it has proven to be extremely difficult. The problem can be posed as edge-colouring. The Ramsey number R(k,l) is the smallest number such that if we two-colour the edges of complete graph of this size, there always exists a monochromatic sub-graph of either k or l nodes.

A related problem (which is often called the Ramsey problem) is to colour the edges of a complete graph with n nodes using at most k colours, in such a way that there is no monochromatic triangle in the graph, i.e. in any triangle at most two edges have the same colour. With 3 colours, the problem has a solution if n < 17.

There exist various interesting generalizations of Ramsey numbers (e.g. to hypergraphs, to graphs which are complete except for a limited number of edges, or to infinite size graphs).

Schur’s lemma is closely related, and is described in prob015.