Ramsey theory

Ramsey theory is a field of mathematics (specifically combinatorics, the mathematics of counting and countable structures) that studies how large, arbitrary structures must have smaller, more orderly substructures. It is named after the British mathematician and philosopher Frank Plumpton Ramsey (19031930).

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

 Examples 
A common introduction to Ramsey theory is called the theorem on friends and strangers: at any party with at least six people, there are always three people who are either (a) mutual acquaintances (each one knows the other two) or (b) mutual strangers (each one does not know either of the other two).

This is a representation of a problem in graph theory. 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? Ramsey theory shows that the answer is 6. These sizes are called Ramsey numbers; in the language of Ramsey theory, we say "the Ramsey number for red three and blue three is six".

Ramsey theory is now a complete branch of mathematics.

 Notes 

Category:Graph  theory