Ramsey Theory - Examples

Examples

A typical result in Ramsey theory starts with some mathematical structure that is then cut into pieces. How big must the original structure be in order to ensure that at least one of the pieces has a given interesting property?

For example, consider a complete graph of order n; that is, there are n vertices and each vertex is connected to every other vertex by an edge. A complete graph of order 3 is called a triangle. Now colour every edge red or blue. How large must n be in order to ensure that there is either a blue triangle or a red triangle? It turns out that the answer is 6. See the article on Ramsey's theorem for a rigorous proof.

Another way to express this result is as follows: at any party with at least six people, there are three people who are all either mutual acquaintances (each one knows the other two) or mutual strangers (each one does not know either of the other two). See theorem on friends and strangers.

This also is a special case of Ramsey's theorem, which says that for any given integer c, any given integers n₁,...,n_c, there is a number, R(n₁,...,n_c), such that if the edges of a complete graph of order R(n₁,...,n_c) are coloured with c different colours, then for some i between 1 and c, it must contain a complete subgraph of order n_i whose edges are all colour i. The special case above has c = 2 and n₁ = n₂ = 3.