The Infinite Ramsey Theorem for Uniform Hypergraphs

From Pairs to Uniform Hypergraphs

A graph records which pairs of vertices are joined. A uniform hypergraph generalizes this idea: its edges may contain more than two vertices. The infinite Ramsey theorem says that if the edges of a countably infinite uniform hypergraph receive finitely many colors, some infinite set of vertices has all its edges the same color. The key is to stabilize the color seen by each already chosen set as later vertices are added. This converts an \(r\)-uniform coloring into a coloring of \((r-1)\)-element sets, where induction applies.

Write \([X]^r\) for the collection of all \(r\)-element subsets of a set \(X\). A finite coloring is a function \(c:[X]^r\to\{1,\dots,q\}\), where \(q\) is a positive integer. A set \(H\subseteq X\) is homogeneous for \(c\) if \(c\) has one constant value on \([H]^r\). Equivalently, every \(r\)-element subset of \(H\) receives the same color. We consider positive integers \(r\), and \(X\) is countably infinite.

It is enough to prove the result for \(X=\mathbb{N}=\{1,2,3,\dots\}\). Indeed, a bijection from \(\mathbb{N}\) to \(X\) transfers each coloring to one on \([\mathbb{N}]^r\), and transfers any infinite homogeneous subset back to \(X\). We prove the theorem by induction on \(r\). The base case is the infinite pigeonhole principle; the induction step relies on a finite sequence of infinite thinnings.

The Infinite Thinning Step

Proof. For each color \(i\in\{1,\dots,q\}\), let \(A_i=\{a\in A:f(a)=i\}\). These \(q\) sets cover \(A\). If every \(A_i\) were finite, their finite union would be finite, contradicting that \(A\) is infinite. Therefore some \(A_i\) is infinite, and \(f\) is constant on that set. \(\square\)

The lemma can be applied repeatedly to stabilize finitely many coloring conditions at once. After each application the remaining set is still infinite, so the next condition can be handled without losing the possibility of making further choices.

Proof by Induction on Uniformity

For \(r=1\), the theorem is exactly the lemma: the coloring assigns a color to each individual element, and one color occurs infinitely often. Now let \(r\ge2\), assume the theorem holds for \((r-1)\)-element subsets of every countably infinite set, and consider a coloring \(c:[\mathbb{N}]^r\to\{1,\dots,q\}\).

We construct increasing integers \(x_1,x_2,\dots\) and nested infinite sets \(A_0,A_1,\dots\). Start with \(A_0=\mathbb{N}\). At stage \(n\), choose \(x_n\) to be the least element of \(A_{n-1}\), and set \(B_n=A_{n-1}\setminus\{x_n\}\). The set \(B_n\) is infinite, and it contains none of \(x_1,\dots,x_n\). Let \(X_n=\{x_1,\dots,x_n\}\).

For every \(S\in[X_n]^{r-1}\), consider the function on \(B_n\) given by \(y\mapsto c(S\cup\{y\})\). Its argument \(y\) is not in \(S\), so \(S\cup\{y\}\) has exactly \(r\) elements and the color is defined. There are finitely many such sets \(S\). Apply the lemma successively to these functions, each time restricting the current infinite set to an infinite constant-color subset. Call the final infinite set \(A_n\). If there are no such \(S\), take \(A_n=B_n\). In either case \(A_n\subseteq B_n\), and for every \(S\in[X_n]^{r-1}\) there is a color \(d_n(S)\) such that

Set \(X_\infty=\{x_1,x_2,\dots\}\). Define a coloring \(d\) of \([X_\infty]^{r-1}\) as follows. Given \(S\in[X_\infty]^{r-1}\), let \(n\) be the stage by which all elements of \(S\) have been chosen, and put \(d(S)=d_n(S)\). This definition is independent of choosing a later stage instead: every later remaining set is contained in \(A_n\), so the color of \(S\cup\{y\}\) stays \(d_n(S)\) for all later choices \(y\).

The set \(X_\infty\) is countably infinite, so the induction hypothesis applied to \(d\) gives an infinite \(H\subseteq X_\infty\) and a color \(\gamma\) such that \(d(S)=\gamma\) for every \(S\in[H]^{r-1}\). Take any \(T\in[H]^r\) and write its elements in increasing order as \(t_1<\cdots<t_r\). Let \(S=\{t_1,\dots,t_{r-1}\}\). At the stage when all elements of \(S\) have been chosen, the last element \(t_r\) belongs to the remaining set \(A_n\), because it is a later chosen element. Thus

This holds for every \(T\in[H]^r\), so \(H\) is homogeneous for \(c\). The induction step is complete, and hence the theorem holds for every positive integer \(r\). \(\square\)

Worked Applications

What the Stabilization Accomplishes

The induction does not assert that the original coloring is already determined by the first \(r-1\) elements of a set. Instead, for each fixed \((r-1)\)-set \(S\) of selected elements, the construction makes \(c(S\cup\{y\})\) constant as \(y\) ranges over all later selected elements. The induced coloring \(d(S)\) records precisely that stable value. Homogeneity for \(d\), followed by the stabilization property, then gives homogeneity for the original coloring.

For \(r=2\), the construction turns a coloring of pairs into a coloring of single vertices: each selected vertex receives the color that all its later selected neighbors have with it. An infinite set on which those recorded colors agree is homogeneous for the original pair coloring. For larger \(r\), the same argument lowers the uniformity by one, and induction repeats that reduction until the one-element case.

Common pitfall: confusing the derived color with every original color. For the triple-sum coloring in the first example, the pair \(\{1,2\}\) does not have one color with every possible third element: \(\{1,2,3\}\) has sum \(1+2+3=6\), which is even, whereas \(\{1,2,4\}\) has sum \(1+2+4=7\), which is odd. It would be wrong to assign \(\{1,2\}\) a stable color before restricting the possible third elements. The construction first thins to an infinite set on which the color is constant for that pair, and does so simultaneously for every pair of already selected elements. Only then is the derived coloring defined.

The theorem applies to any finite number of colors and any fixed positive uniformity. It is an existence result: the nested thinning proof produces a set through successive choices, but it does not promise a simple description of that set for an arbitrary coloring.