= Ramsey theory
{c}
{wiki}
Ramsey theory studies configurations that every <finite coloring> of a sufficiently large structure must contain. Its striking message is that some order is unavoidable even when no organized construction was used. A basic example is the <Ramsey number for triangles>: color every <edge> of a <complete graph> on six <vertices> red or blue, in any way, and some <triangle in a graph> has all three <edges> the same color. Five <vertices> do not suffice.
The objects receiving colors matter. In the <Ramsey number for triangles>, colors belong to <edges>, which represent all <unordered pairs> of distinct <vertices>; the <vertices> themselves have no colors. In the <finite Ramsey theorem>, colors can instead belong to all $r$-element <subsets> of a <finite set>. A <monochromatic set> or <homogeneous set for a colouring> expresses agreement among the appropriate colored objects.
Why is this useful? <Ramsey theory> provides existence guarantees in <combinatorics> that survive every possible assignment of a fixed finite number of colors. The <Ramsey theorem> turns this into a structural dichotomy: every sufficiently large <graph> contains a large <clique> or a large <independent set>. In <arithmetic>, the <Van der Waerden theorem> guarantees <monochromatic> <arithmetic progressions>. The beauty is the universal quantifier: an adversary can choose every color and still cannot prevent the promised configuration.
These guarantees concern precisely specified configurations under stated hypotheses. They do not justify selecting arbitrary patterns in empirical data after seeing the data, or attributing <statistical significance> to a selected pattern. A mathematical guarantee of some <monochromatic> configuration alone says nothing about the empirical meaning of that configuration.
The subject's name comes from F. P. Ramsey's https://doi.org/10.1112/plms/s2-30.1.264[1930 paper, "On a Problem of Formal Logic"]{ref}. The https://www.cs.umd.edu/~gasarch/BLOGPAPERS/ramseyorig.pdf[original paper, pp. 264-268, Theorems A and B]{ref} records receipt on 28 November 1928 and presentation on 13 December 1928. Ramsey introduced the <Ramsey theorem for r-sets> and <finite Ramsey theorem> as tools for a problem in <mathematical logic>, while recognizing their independent interest in <combinatorics>. He also distinguished proving that a finite threshold exists from finding its smallest value, the quantitative question captured by a <Ramsey number>.
Back to article page
