| proposed by | Toby Walsh tw@cs.york.ac.uk |
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).