Ramsey theory

From Wikipedia, the free encyclopedia
Jump to: navigation, search

The Ramsey theory is named after the British mathematician and philosopher Frank Ramsey (1903–1930). It is a branch of mathematics that studies the conditions under which order must appear.[1]

Examples[change | change source]

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

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.

Another way to express this result is as follows: at any party with at least six people, there are 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).

Ramsey theory is now a complete branch of mathematics.

Notes[change | change source]

  1. "Order" in the sense of structure or regularity.