Homogeneous Pairs Inside an Infinite Set
A finite coloring assigns one of finitely many colors to each pair of distinct elements. Even if the coloring varies irregularly across a countably infinite set, some infinite subset has all its pairs the same color. The proof does not try to make every chosen pair agree at once. Instead, it repeatedly narrows an infinite set of candidates so that each newly chosen element has a uniform color to all later candidates. A final infinite pigeonhole argument then selects stages with the same color.
Let \(X\) be a countably infinite set. Write \([X]^2\) for the set of its two-element subsets, so each element of \([X]^2\) is an unordered pair of distinct elements of \(X\). A coloring with \(r\) colors is a function \(c:[X]^2\to\{1,\dots,r\}\), where \(r\) is a positive integer. A subset \(H\subseteq X\) is homogeneous if there is a color \(a\) such that \(c(\{u,v\})=a\) for every pair of distinct \(u,v\in H\). The color \(a\) is allowed to depend on the coloring.
The essential finite-color fact is that an infinite set cannot be divided into finitely many finite pieces.
Proof. Suppose the partition has \(r\) parts and every part is finite. The union of finitely many finite sets is finite: its size is the sum of the finitely many finite sizes of the parts. The union would therefore be finite, contradicting that it is the original infinite set. Hence at least one part is infinite. \(\square\)
The Nested-Candidate Construction
Enumerate the elements of \(X\) as \(x_1,x_2,\dots\), with no repetitions. The proof constructs chosen elements \(v_1,v_2,\dots\), infinite candidate sets \(A_1,A_2,\dots\), and colors \(a_1,a_2,\dots\). At stage \(i\), the chosen element \(v_i\) will have color \(a_i\) to every element still in \(A_i\). Each later candidate set will be contained in the earlier ones, so all later chosen elements retain that property.
Set \(A_0=X\). At stage \(i\), choose \(v_i\in A_{i-1}\). Remove \(v_i\), leaving the infinite set \(A_{i-1}\setminus\{v_i\}\).
Partition \(A_{i-1}\setminus\{v_i\}\) according to the color of the pair \(\{v_i,y\}\). There are finitely many color classes, so the infinite pigeonhole principle gives an infinite class. Call its color \(a_i\) and set that class to be \(A_i\).
The sequence \(a_1,a_2,\dots\) uses only finitely many colors. Some color occurs at infinitely many indices; retain the chosen vertices at those indices.
The construction makes \(A_i\subseteq A_{i-1}\setminus\{v_i\}\), and every \(y\in A_i\) satisfies \(c(\{v_i,y\})=a_i\). Thus each set is infinite, and the sets are nested. In particular, all chosen vertices are distinct: once \(v_i\) is chosen, it is excluded from \(A_i\) and every later candidate set.
Proof of the theorem. Carry out the construction above. Since the sequence \(a_1,a_2,\dots\) takes values in the finite set \(\{1,\dots,r\}\), the infinite pigeonhole principle gives a color \(a\) and an infinite set of indices \(I\) such that \(a_i=a\) for every \(i\in I\). Define \(H=\{v_i:i\in I\}\), which is infinite because the chosen vertices are distinct. Take any two distinct elements of \(H\), say \(v_i\) and \(v_j\) with \(i<j\). At stage \(i\), \(v_j\) belongs to \(A_i\): indeed, \(v_j\in A_{j-1}\), and the nesting of the candidate sets gives \(A_{j-1}\subseteq A_i\). The defining property of \(A_i\) therefore gives \(c(\{v_i,v_j\})=a_i=a\). This holds for every pair from \(H\), so \(H\) is homogeneous. \(\square\)
The order of the two selection steps matters. At each stage the construction first makes the color uniform from the current vertex to all remaining candidates. Only after building this sequence does it use finiteness of the color set to find infinitely many stages of one color. It does not require the colors \(a_i\) to be the same at every stage.
Worked Applications of the Construction
Worked Example: Pair Color Determined by Parity
Let \(X=\{1,2,3,\dots\}\). Color \(\{i,j\}\) red when \(i+j\) is even and blue when \(i+j\) is odd. Follow a possible nested-candidate construction, starting with \(A_0=X\).
Choose \(v_1=1\). For a candidate \(j>1\), the sum \(1+j\) is odd exactly when \(j\) is even. Choose the infinite blue class \(A_1=\{2,4,6,\dots\}\), so \(a_1\) is blue. Next choose \(v_2=2\) from \(A_1\). After removing \(2\), every candidate in \(\{4,6,8,\dots\}\) gives an even sum with \(2\), so choose \(A_2=\{4,6,8,\dots\}\) and \(a_2\) red. Then choose \(v_3=4\); every element of \(A_3=\{6,8,10,\dots\}\) gives an even sum with \(4\), so \(a_3\) is red.
Continuing, at stage \(i\ge2\), choose \(v_i=2i-2\) and \(A_i=\{2i,2i+2,2i+4,\dots\}\). Each candidate is even, so its sum with \(v_i\) is even and \(a_i\) is red. The red color occurs at every stage \(i\ge2\), giving \(H=\{2,4,6,\dots\}\).
Check: for any distinct \(2p,2q\in H\), their sum is \(2p+2q=2(p+q)\), which is even. Thus every pair in \(H\) is red, as the construction predicts. The first chosen vertex \(1\) is not needed in this homogeneous subset.
Worked Example: Pair Color Determined by a Difference Modulo Three
Again let \(X=\{1,2,3,\dots\}\), now with colors \(0,1,2\). For \(i<j\), color \(\{i,j\}\) by the remainder of \(j-i\) upon division by \(3\). Choose \(v_1=1\). The candidates \(4,7,10,\dots\) all differ from \(1\) by a multiple of \(3\), so take \(A_1=\{4,7,10,\dots\}\) and \(a_1=0\).
Choose \(v_2=4\) from \(A_1\). The candidates \(7,10,13,\dots\) all differ from \(4\) by a multiple of \(3\), so take \(A_2=\{7,10,13,\dots\}\) and \(a_2=0\). Next choose \(v_3=7\) and \(A_3=\{10,13,16,\dots\}\), again with \(a_3=0\). In general, choose \(v_i=3i-2\) and \(A_i=\{3i+1,3i+4,3i+7,\dots\}\). Each \(y\in A_i\) has \(y-v_i\) a positive multiple of \(3\), so every stage has color \(0\).
The construction therefore produces the infinite homogeneous set \(H=\{1,4,7,10,\dots\}\).
Check: if \(3p+1<3q+1\) are two elements of \(H\), their difference is \((3q+1)-(3p+1)=3(q-p)\), which has remainder \(0\) on division by \(3\). Hence every pair in \(H\) has color \(0\).
Worked Example: A Coloring Based on Powers of Two
Let \(X=\{1,2,3,\dots\}\). Color \(\{i,j\}\), for \(i<j\), red if \(i\) is a power of \(2\), and blue otherwise. Use \(v_i=i\) and \(A_i=\{n:n>i\}\). These are valid candidate sets: at stage \(i\), every candidate \(n>i\) forms a pair whose smaller element is \(i\), so the color is the same for all candidates. The stage color \(a_i\) is red exactly when \(i\) is a power of \(2\).
The red stages include \(1,2,4,8,16,\dots\), an infinite sequence. Retaining those stages gives \(H=\{1,2,4,8,16,\dots\}\), the positive powers of \(2\).
Check: take any two distinct elements \(2^p<2^q\) of \(H\), where \(p<q\) are nonnegative integers. Their smaller element is \(2^p\), which is a power of \(2\), so their pair is red. Thus \(H\) is homogeneous even though the coloring on all of \(X\) is not constant.
Why the Extraction Step Is Necessary
A common mistake is to assume that the nested candidate sets make the entire chosen sequence homogeneous. They do not: they guarantee that the color from \(v_i\) to later chosen vertices is \(a_i\), and \(a_i\) can vary with \(i\). The parity example gives a concrete failure. Its construction has \(v_1=1\), \(a_1\) blue, \(v_2=2\), and \(a_2\) red. The pair \(\{v_1,v_2\}=\{1,2\}\) is blue because \(1+2=3\) is odd, while \(\{v_2,v_3\}=\{2,4\}\) is red because \(2+4=6\) is even. The sequence \(v_1,v_2,v_3,\dots\) is therefore not homogeneous.
The correction is to apply the infinite pigeonhole principle to the stage colors, not to claim that they were already constant. In that same example, every stage \(i\ge2\) has red stage color, so retaining those stages gives the homogeneous set of positive even integers. In the general proof, the same step works because finitely many colors cannot each occur at only finitely many stages.
Finiteness of the color set is an essential hypothesis of this argument: it is what guarantees an infinite set of stages sharing one color. The theorem also promises some homogeneous color, not a color chosen in advance. For example, a coloring that assigns every pair blue has no red homogeneous subset, although it does have an infinite blue one.
The nested construction is useful because it separates two requirements that are easy to confuse. First, each chosen vertex must have a uniform color to all future candidates; this is ensured by passing to an infinite color class. Second, the chosen vertices must share one common color across stages; this follows by retaining infinitely many stages with the same color. Together, these steps turn a finite-coloring condition on pairs into an infinite homogeneous set.
Check Your Understanding
For each question, identify how the candidate sets or the stage colors are being used.
- In the nested-candidate proof, why does removing the chosen element \(v_i\) leave an infinite set?
- Why must some color occur at infinitely many stages in the sequence \(a_1,a_2,\dots\)?
- For the coloring of positive integers by the remainder of \(j-i\) modulo \(3\), verify directly that \(\{2,5,8,11,\dots\}\) is homogeneous.
- In the parity example, what color is assigned to \(\{3,7\}\), and what color is assigned to \(\{3,6\}\)?
- Which step of the proof would fail if pairs could be assigned infinitely many different colors?