Ramsey's theorem

:This article goes into technical details quite quickly. For a slightly gentler introduction see Ramsey theory.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

In combinatorics, Ramsey's theorem states that in colouring a large complete graph (that is a simple graph, where an edge connects every pair of vertices), one will find complete subgraphs all of the same colour. In a precise statement, for any pair of positive integers (r,s), there exists an integer R(r,s) such that for any complete graph on R(r,s) vertices, whose edges are coloured red or blue, there exists either a complete subgraph on r vertices which is entirely blue, or a complete subgraph on s vertices which is entirely red. Here R(r,s) signifies an integer that depends on both r and s.

Related Topics:
Combinatorics - Complete graph - Simple graph - Edge - Vertices

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

Ramsey's theorem is a foundational result in combinatorics. The first version of this result was proved by F. P. Ramsey. This initiated the combinatorial theory, now called Ramsey theory, that seeks regularity amid disorder: general conditions for the existence of substructures with regular properties. In this application it is a question of the existence of homogeneous subsets, that is, subsets connected edges of just one colour.

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

An extension of this theorem applies to any finite number of colours, rather than just two. More precisely, the theorem states that for any given number of colors c, and any given integers n1,...,nc, there is a number, R(n1, ..., nc; c), such that if the edges of a complete graph of

~ ~ ~ ~ ~ ~ ~ ~ ~ ~

order R(n1, ..., nc; c) are colored with c different colors, then for some i between 1 and c, it must contain a complete subgraph of order ni whose edges are all color i. The special case above has c = 2 (and n1 = r and n2 = s).

~ ~ ~ ~ ~ ~ ~ ~ ~ ~