= Finite Ramsey theorem
{title2=$\exists n\quad[n]\longrightarrow(m)^r_k$}
Fix <positive integers> $r,k,m$ with $m\geq r$. There is an <integer> $n\geq m$, depending only on $r,k,m$, such that every <finite coloring>
$$
c:\binom{[n]}{r}\longrightarrow\{1,\ldots,k\}
$$
has a <subset> $H\subseteq[n]$ of size $m$ for which the <restriction of a function> $c$ to $\binom{H}{r}$ is a <constant function>. Here $[n]=\{1,\ldots,n\}$, and $\binom{S}{r}$ denotes the collection of all $r$-element <subsets> of $S$, rather than its <binomial coefficient> <cardinality>. The notation $[n]\longrightarrow(m)^r_k$ 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 https://www.cs.umd.edu/~gasarch/BLOGPAPERS/ramseyorig.pdf[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.
Back to article page
