Ramsey theory

Ramsey theory, named for Frank P. Ramsey, is a branch of mathematics that studies the degree to which structure is ubiquitous. Problems in Ramsey Theory take this form: Take a mathematical structure of some type, and break it into pieces. How big must the original structure be in order to ensure that one of the pieces still has a sufficient amount of structure? An oft-quoted slogan for the subject is "Complete disorder is impossible".

For example, suppose you have a complete graph of order n; this means you have n vertices (dots) where each vertex is connected to every other vertex by an edge (a line). A complete graph of order 3 is called a triangle. Color 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; that is, in order to guarantee that there are three vertices each of which is connected to the others by edges of the same color? It turns out that the answer is 6. See the Ramsey's theorem article for a rigorous proof.

Another way to interpret this: at any party with at least six people, there are either three people who are all mutual acquaintances (each one knows the other two) or mutual strangers (each one does not know either of the other two).

This 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;c), such that if the edges of a complete graph of order R(n₁,...,n_c;c) are colored with c different colors, then for some i between 1 and c, it must contain a complete subgraph of order n_i whose edges are all color i. The special case above has c = 2 and n₁ = n₂ = 3.

Two other key theorems of Ramsey theory are:

Van der Waerden's theorem

For any given c and n, there is a number V, such that if the elements of an arithmetic progression of V numbers are colored with c different colors, then it must contain an arithmetic progression of length n whose elements are all the same color.

Hales-Jewett theorem[?]

For any given n, and c, there is a number H such that if the cells of a H-dimensional n×n×n×...×n cube are colored with c colors, there must be one row, column, etc. of length n all of whose cells are the same color. That is, if you play on board with sufficiently many directions, then tic-tac-toe-n-in-a-row is a forced win for the first player, no matter how large n is, and no matter how many people are playing.