Infinite Ramsey Statements for Finite Subsets

Coloring Finite Subsets

Ramsey theory asks whether a coloring of a sufficiently large structure must contain a regular part. In the infinite setting, the structure can be the natural numbers, and the objects being colored can be subsets of one fixed size. The central assertion is that finitely many colors cannot prevent the existence of an infinite set whose subsets of that size all have one color.

Write \(\mathbb N=\{1,2,3,\ldots\}\). For a positive integer \(r\), the notation \([\mathbb N]^r\) means the collection of all subsets of \(\mathbb N\) containing exactly \(r\) elements. Thus an element of \([\mathbb N]^2\) is an unordered pair \(\{i,j\}\) with \(i\ne j\), while an element of \([\mathbb N]^3\) is an unordered triple of distinct natural numbers. More generally, for \(A\subseteq\mathbb N\), \([A]^r\) is the collection of all \(r\)-element subsets of \(A\).

Definition: A finite coloring of \([\mathbb N]^r\) is a function \(c:[\mathbb N]^r\to C\), where \(C\) is a finite nonempty set of colors. A set \(H\subseteq\mathbb N\) is homogeneous for \(c\) if there is one color \(\gamma\in C\) such that \(c(S)=\gamma\) for every \(S\in[H]^r\). It is an infinite homogeneous set if, in addition, \(H\) is infinite.

The coloring is a function on subsets, not on ordered lists. When a rule uses the entries of a pair or triple, write them in increasing order to evaluate the rule. The definition does not require the color \(\gamma\) to be specified in advance: the coloring and the homogeneous set determine it. Since an infinite set contains \(r\)-element subsets for every fixed positive integer \(r\), the condition is not vacuous for an infinite \(H\).

The Infinite Ramsey Theorem

Theorem (Infinite Ramsey Theorem): Let \(r\ge 1\) and \(q\ge 1\) be integers. For every coloring \(c:[\mathbb N]^r\to\{1,\ldots,q\}\), there is an infinite set \(H\subseteq\mathbb N\) such that \(c\) is constant on \([H]^r\). In other words, there is a color \(i\in\{1,\ldots,q\}\) for which \(c(S)=i\) for every \(S\in[H]^r\).

The hypotheses fix both the subset size \(r\) and the finite number \(q\) of available colors. The conclusion supplies an infinite set, not merely a large finite set, and every \(r\)-element subset of that set must receive the same color. The theorem does not say that all of \(\mathbb N\) is homogeneous, nor that an arbitrarily chosen infinite subset is homogeneous.

The theorem is stated here as a standard result; its proof is developed in later material. Two elementary facts help clarify its quantifiers and how homogeneous sets behave.

Proposition: The Infinite Ramsey Theorem holds when \(r=1\): every finite coloring of \([\mathbb N]^1\) has an infinite homogeneous set.

Proof. Let \(c:[\mathbb N]^1\to\{1,\ldots,q\}\) be a coloring, and for each color \(i\) define \(A_i=\{n\in\mathbb N:c(\{n\})=i\}\). These \(q\) sets cover \(\mathbb N\), because each singleton receives one of the \(q\) colors. If every \(A_i\) were finite, their finite union would be finite. That contradicts the fact that their union is \(\mathbb N\), which is infinite. Thus some \(A_i\) is infinite. For every \(n\in A_i\), the singleton \(\{n\}\) has color \(i\), so \(A_i\) is an infinite homogeneous set. \(\square\)

Proposition: If \(H\) is homogeneous for a coloring \(c:[\mathbb N]^r\to C\), then every infinite subset \(H'\subseteq H\) is homogeneous for \(c\) in the same color.

Proof. Since \(H\) is homogeneous, there is a color \(\gamma\in C\) such that \(c(S)=\gamma\) for every \(S\in[H]^r\). If \(H'\subseteq H\), then every \(S\in[H']^r\) is also in \([H]^r\). Therefore \(c(S)=\gamma\) for every \(S\in[H']^r\). If \(H'\) is infinite, it is an infinite homogeneous set, with the same color \(\gamma\). \(\square\)

Worked Pair Colorings

Worked Example: Coloring Pairs by the Parity of Their Sum

Define \(c:[\mathbb N]^2\to\{0,1\}\) as follows: for a pair \(\{i,j\}\), write its elements with \(i<j\), and let \(c(\{i,j\})\) be the remainder when \(i+j\) is divided by \(2\). Find an infinite homogeneous set.

Take \(H=\{2n:n\in\mathbb N\}\), the positive even integers. If \(\{2a,2b\}\in[H]^2\), then \(a\ne b\), and its sum is \(2a+2b=2(a+b)\). Dividing by \(2\) leaves remainder \(0\), so \(c(\{2a,2b\})=0\) for every pair in \([H]^2\). The set \(H\) is infinite because it contains one distinct element \(2n\) for each positive integer \(n\). Hence \(H\) is infinite and homogeneous in color \(0\).

Check: For the pair \(\{2,8\}\), the sum is \(2+8=10\), and \(10\) has remainder \(0\) on division by \(2\). For \(\{6,14\}\), the sum is \(6+14=20\), which also has remainder \(0\). The calculation for a general pair in \(H\) gives the same color, not just these two checks.

Worked Example: Coloring Pairs by Their Difference Modulo Three

For \(i<j\), color \(\{i,j\}\) by the remainder of \(j-i\) on division by \(3\). This defines a coloring \(c:[\mathbb N]^2\to\{0,1,2\}\). Let \(H=\{3n:n\in\mathbb N\}\). For any distinct positive integers \(a,b\), put them in increasing order so that \(a<b\). The corresponding elements of \(H\) are \(3a<3b\), and their difference is \(3b-3a=3(b-a)\). Its remainder on division by \(3\) is \(0\); thus every pair from \(H\) has color \(0\).

For instance, the pair \(\{3,12\}\) has increasing entries \(3<12\), so its difference is \(12-3=9\). Since \(9=3\cdot3+0\), its color is \(0\). The pair \(\{6,15\}\) has difference \(15-6=9=3\cdot3+0\), also color \(0\). The general calculation proves that \(H\) is homogeneous, and \(H\) is infinite because its elements \(3n\) are distinct as \(n\) ranges over \(\mathbb N\).

Check: The rule always subtracts the smaller entry from the larger one. For a pair \(\{3a,3b\}\) with \(a<b\), the difference is exactly \(3(b-a)\), a multiple of \(3\), so there is no other possible remainder or color on \(H\).

Worked Triple Coloring

Worked Example: Coloring Triples by Their Sum Modulo Three

Define \(c:[\mathbb N]^3\to\{0,1,2\}\) by adding the three elements of a triple and taking the remainder on division by \(3\). Let \(H=\{3n:n\in\mathbb N\}\). Any triple in \([H]^3\) has the form \(\{3a,3b,3d\}\), where \(a,b,d\) are distinct positive integers. Its sum is \(3a+3b+3d=3(a+b+d)\), which has remainder \(0\) on division by \(3\). Therefore every triple from \(H\) has color \(0\).

For a numerical check, the triple \(\{3,6,12\}\) has sum \(3+6+12=21\). Since \(21=3\cdot7+0\), its color is \(0\). The triple \(\{6,9,15\}\) has sum \(6+9+15=30\), and \(30=3\cdot10+0\), so its color is \(0\) as well. These examples agree with the general calculation. The set \(H\) is infinite, so this is an infinite homogeneous set for a coloring of triples.

This example uses \(r=3\): each colored object has exactly three distinct elements. The theorem’s conclusion concerns all triples selected from the one set \(H\), not just a chosen collection of triples. The same notation \([H]^r\) expresses that requirement for any fixed positive \(r\).

Scope and Common Pitfalls

The theorem is an existence statement for each fixed finite coloring of each fixed subset size. Its quantifiers can be read in order: choose \(r\), choose \(q\), and choose the coloring \(c\); then there exists an infinite \(H\), which may depend on all these choices. It does not specify a formula for \(H\), and the theorem by itself is not a procedure for finding one for an arbitrary coloring.

For \(r=2\), the colored objects are pairs, which can be viewed as the edges of a complete graph on \(\mathbb N\). For \(r=3\), the colored objects are triples. This change in \(r\) changes the objects to which the coloring applies; it does not change the meaning of homogeneous. In either case, every relevant subset of \(H\) must receive the same color.

Common mistake: treating a subset as an ordered tuple. In the difference example, the pair \(\{3,6\}\) is one object. Its entries are sorted as \(3<6\), so the difference used by the definition is \(6-3=3\), whose remainder modulo \(3\) is \(0\). Reversing the entries and computing \(3-6=-3\) is not the stated rule: the coloring is defined by taking the larger entry minus the smaller entry. For a sum coloring, order does not affect the sum, but the objects are still subsets, and repeated entries are not allowed.

A second error is to check only a few subsets and then declare an infinite set homogeneous. A finite list of checks can illustrate the rule, but homogeneity requires one color for every \(r\)-element subset of \(H\). In the worked examples, the general algebraic calculation verifies that universal condition; the numerical checks serve only as confirmation.

Check Your Understanding

For each question, keep the subset size fixed and apply the definition to all subsets of that size.

Write out the meaning of \([\{2,4,7,9\}]^2\). How many elements does each member of this collection contain?
For the pair coloring by the parity of the sum, determine the color of \(\{5,10\}\) and \(\{7,12\}\).
For the coloring by pair differences modulo \(3\), determine the color of \(\{4,11\}\), using the smaller entry first.
For the triple coloring by sum modulo \(3\), determine the color of \(\{2,7,12\}\).
Explain why an infinite subset of a homogeneous set remains homogeneous in the same color.