Use for questions in Ramsey Theory, i.e. regarding how large a structure must be before it is guaranteed to have a certain property. Please be especially careful not to ask open questions in this tag.
Please be especially careful not to ask open questions in this tag.
Ramsey theory refers to questions of the form "how large must a structure be before it is guaranteed to have a certain property?" Often, the theme is that in a sufficiently large structure, a highly ordered substructure will appear.
A relatively simple example of a result in Ramsey theory is the Theorem on Friends and Strangers.
In any party of at least six people either at least three of them are (pairwise) mutual strangers or at least three of them are (pairwise) mutual acquaintances.
Other well-known results in Ramsey theory include:
- Ramsey's theorem, which generalizes the Theorem on Friends and Strangers to larger subgroups than size $3$. Many other problems in Ramsey theory are variations on this result, and involve coloring graphs.
- Schur's theorem, which says that for any $r$, there exists a sufficiently large $N$ such that whenever the integers $1, 2, \dots, N$ are each given one of $r$ colors, there will be three integers $x, y, x+y$ all of the same color. More generally, additive Ramsey theory deals with results about the integers and other additive groups, including results such as Van der Waerden's theorem.
- The Hales–Jewett theorem which, informally, states that for any parameters $t$ and $r$ there is a sufficiently large dimension such that any $r$-coloring of a $t \times t \times \dots \times t$ grid contains a monochromatic line. More generally, Euclidean Ramsey theory deals with results about geometric objects.
Proofs in Ramsey theory often give extremely large bounds on how large a structure must be before it has the desired property.
A standard introduction to the area is the textbook Ramsey Theory by Graham, Rothschild, and Spencer.
