Ramsey theory

Lore & Background

Ramsey theory is named after the British mathematician and philosopher Frank P. Ramsey. Problems in Ramsey theory typically ask a question of the form: 'how big must some structure be to guarantee that a particular property holds?' A typical result starts with some mathematical structure that is cut into pieces, asking how large the original structure must be to ensure at least one piece has a given interesting property, a concept defined as partition regularity. For example, consider a complete graph of order n with edges colored red or blue; it turns out that n must be at least 6 to guarantee either a blue triangle or a red triangle. This is a special case of Ramsey's theorem, which states that for any given integer c and any given integers n1,...,nc, there is a number R(n1,...,nc) such that if the edges of a complete graph of that order are colored with c different colors, then for some i it must contain a complete subgraph of order ni whose edges are all color i.

Reader's Guide

Ramsey theory is significant because it reveals that sufficiently large structures inevitably contain ordered substructures, a principle with broad applications in mathematics. Two key theorems are Van der Waerden's theorem, which guarantees arithmetic progressions in colored numbers, and the Hales–Jewett theorem, which implies that multi-player tic-tac-toe on a sufficiently high-dimensional board cannot end in a draw. Results in Ramsey theory are often unconstructive, showing existence without providing a method to find the structure other than brute-force search. The bounds required for these results are often enormously large, growing exponentially or even as fast as the Ackermann function; Graham's number, one of the largest numbers ever used in a serious mathematical proof, is an upper bound for a Ramsey theory problem. Theorems in Ramsey theory generally assert that in every partition of a large structured object, one class necessarily contains its own structured object, or that the largest partition class always contains the desired substructure (density results or Turán-type results). Notable examples include Szemerédi's theorem and the density version of the Hales-Jewett theorem.

Did You Know?

• Ramsey theory is named after the British mathematician and philosopher Frank P. Ramsey.
• A classic result states that at any party with at least six people, there are three mutual acquaintances or three mutual strangers.
• Graham's number, one of the largest numbers ever used in serious mathematical proof, is an upper bound for a Ramsey theory problem.
• The Hales–Jewett theorem implies that multi-player n-in-a-row tic-tac-toe cannot end in a draw if played on a board with sufficiently many dimensions.