 Finite Ramsey theorem

Fix positive integers $r,k,m$ with $m\ge r$. There is an integer $n\ge m$, depending only on $r,k,m$, such that every finite coloringhas a subset $H\subseteq [n]$ of size $m$ for which the restriction of a function $c$ to $\left(\genfrac{}{}{0ex}{}{H}{r}\right)$ is a constant function. Here $[n]=\{1,\dots ,n\}$, and $\left(\genfrac{}{}{0ex}{}{S}{r}\right)$ denotes the collection of all $r$-element subsets of $S$, rather than its binomial coefficient cardinality. The notation $[n]⟶(m{)}_k^r$ abbreviates this property. Thus $H$ is a homogeneous set for a colouring; when $r>1$, the monochromatic set consists of its $r$-element subsets, not its individual elements. This is the finite assertion in Ramsey's original Theorem B, p. 267.

For $r=1$, this is the pigeonhole principle, with sharp threshold $n=k(m-1)+1$. For instance, every red-blue coloring of five objects has three of one color; four objects can split two and two. For $r=2$, $k=2$ and $m=3$, the sharp threshold is six, as shown by the Ramsey number for triangles. Coloring pairs makes this a problem about edges of a complete graph. For larger $r$, the analogous viewpoint uses a hypergraph.

The finite Ramsey theorem lets an existence argument discard most of a large finite set while retaining a prescribed amount of uniform structure. Its threshold applies to every coloring; one does not need an assumption that colors were assigned randomly. A diagonal compactness argument deduces finite existence from Ramsey's theorem, but does not by itself identify the smallest threshold. For pairs, a Ramsey number makes that optimization explicit.