Ramsey Theory

RamseyTheory, named for FrankRamsey, is a branch of mathematics that studies the degree to which structure is ubiquitous. Problems in Ramsey Theory take this form: You have a mathematical structure of some type, and you break it into pieces. How big does the original structure have to be in order to guarantee that one of the pieces still has a sufficient amount of structure?

For example, you have a complete graph of order n; this means you have n dots where each dot is connected to every other dot by an 'edge'. (See GraphTheory.) A complete graph of order 3 is called a triangle. You color every edge red or blue. How large must n be in order to guarantee that there is either a blue triangle or a red triangle; that is, in order to guarantee that there are three dots each of which is connected to the others by edges of the same color? It turns out that the answer is 6.

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 c and n, there is a number, R, such that if the edges of a complete graph of order R are colored with c different colors, then it must contain a complete subgraph of order n whose edges are all one color. The special case above is when c=2 and n=3.

Other theorems of Ramsey Theory are:

VanDerWaerdensTheorem: 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 by n by n by ... by H 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.

RefactorMe: Interesting, but it looks like this (together with VanDerWaerdensTheorem) is a small math WalledGarden. Or am I missing something, that makes this OnTopic?

It's certainly related to ReallyBigNumbers.

CategoryMath