Finite Ramsey Existence from the Infinite Theorem

From Infinite to Finite Ramsey Theory

For fixed clique sizes, the finite Ramsey question asks whether a sufficiently large complete graph must contain a monochromatic clique. The infinite Ramsey theorem for pairs gives a route to an answer, but it applies to a coloring of all pairs of an infinite set, not directly to one finite graph. The key step is to pass from arbitrarily large finite counterexamples to a single coloring whose restrictions agree on every finite set of vertices. That limiting coloring would be a counterexample to the infinite theorem.

Throughout, a red-blue coloring of a complete graph assigns exactly one of the two colors to each edge. A red \(K_s\) is a set of \(s\) vertices all of whose pairs are red; a blue \(K_t\) is defined in the same way. Here \(K_s\) denotes the complete graph on \(s\) vertices. We first take \(s,t\ge 2\).

To prove \(R(s,t)\) exists, it is enough to show that countercolorings cannot have unbounded order. Indeed, if no order had the defining property, then for every positive integer \(n\) there would be a countercoloring of \(K_n\). In particular, we could choose countercolorings on an increasing sequence of orders. The difficulty is that those colorings need not initially agree on their shared vertices. We obtain agreement by repeatedly retaining an infinite set of colorings with the same restriction.

Stabilizing the Finite Restrictions

We use the infinite Ramsey theorem for pairs, established in the earlier material on infinite Ramsey theory: every red-blue coloring of the pairs of a countably infinite set has an infinite subset whose pairs all have the same color. The theorem will apply only after we construct one coloring on all pairs of the natural numbers.

Proof. For each \(i\ge1\), choose a countercoloring \(c_i\) on the vertex set \([n_i]=\{1,\ldots,n_i\}\), where \(n_1<n_2<\cdots\). Such a sequence can be chosen because countercolorings exist at every order: choose \(n_i\) successively larger than \(n_{i-1}\), and take a countercoloring at that order. Let \(I_0\) be the set of all indices \(i\), which is infinite.

We construct infinite index sets \(I_1\supseteq I_2\supseteq\cdots\). Suppose \(I_{k-1}\) has been chosen. Only finitely many indices have \(n_i<k\), so removing them leaves an infinite set of indices for which \(c_i\) is defined on all pairs in \([k]\). A coloring of those pairs has at most \(2^{\binom{k}{2}}\) possible patterns, since there are \(\binom{k}{2}\) pairs and each has two color choices. Partition the remaining indices by their restriction to \([k]\). At least one class is infinite: if every class were finite, the union of the finitely many classes would be finite. Choose one infinite class as \(I_k\). Thus every \(c_i\), for \(i\in I_k\), has the same restriction to \([k]\), and \(I_k\subseteq I_{k-1}\).

For a pair \(\{u,v\}\) of positive integers, let \(k=\max\{u,v\}\). Define its color to be its color in the common restriction to \([k]\) of the colorings indexed by \(I_k\). This is well-defined. In particular, if a later set \(I_\ell\), with \(\ell\ge k\), is used instead, then \(I_\ell\subseteq I_k\), so its colorings have the same restriction to \([k]\).

Now take any set \(S\) of \(s\) positive integers and let \(k\) be its largest element. Choose \(i\in I_k\). The coloring \(c_i\) is defined on \([k]\), and its restriction to \([k]\) agrees with the coloring just defined. Since \(c_i\) contains no red \(K_s\), the pairs in \(S\) are not all red in the new coloring. The identical argument for any set of \(t\) vertices shows that it contains no blue \(K_t\). This constructs the asserted coloring. \(\square\)

The use of an infinite class at each stage matters: it leaves enough indices to stabilize the next, larger restriction. Merely finding many colorings that agree on one fixed vertex set would not be sufficient to define colors consistently on every pair of the positive integers.

Finite Ramsey Numbers Exist

Proof. First suppose \(s,t\ge2\). Assume for contradiction that \(R(s,t)\) does not exist. Then for every positive integer \(n\), some red-blue coloring of \(K_n\) contains neither a red \(K_s\) nor a blue \(K_t\). By the lemma, there is a red-blue coloring of all pairs of the positive integers with neither target clique.

Apply the infinite Ramsey theorem for pairs to this coloring. It gives an infinite set \(H\) whose pairs all have the same color. If that color is red, choose any \(s\) distinct elements of \(H\); every pair among them is red, giving a red \(K_s\). If the color is blue, choose any \(t\) distinct elements of \(H\); they give a blue \(K_t\). Both cases contradict the construction. Therefore a finite order has the Ramsey property, so a least such order exists.

If \(s=1\), every coloring of \(K_1\) contains a red \(K_1\), since a one-vertex clique has no edges whose color needs to be specified. Hence \(R(1,t)=1\). Likewise, \(R(s,1)=1\). This handles the boundary cases and completes the proof. \(\square\)

The theorem is an existence result: it proves that some finite threshold works, without identifying the least threshold or giving a useful numerical bound. The argument depends on both parts of the construction. Stabilization gives a coloring on an infinite set, and the infinite theorem supplies an infinite monochromatic set that must contain either finite target.

Worked Examples

Why the Argument Works—and a Common Pitfall

The proof turns a hypothetical failure of finite existence into an object to which the infinite theorem applies. It does not take a limit of edge colors in a numerical sense. Instead, at stage \(k\), it chooses infinitely many finite colorings that agree exactly on the finite set \([k]\). Because the chosen index sets are nested, the color assigned to any particular pair cannot change at later stages.

A common mistake is to start with countercolorings of larger and larger orders and simply declare that their colors “converge.” There is no reason for an arbitrarily chosen sequence to agree on even one fixed edge: its colors could alternate red and blue. The correction is to pass to an infinite subsequence with a fixed color on the first pair, then an infinite subsequence of that one with a fixed coloring on the first three vertices, and continue. At each finite stage there are only finitely many restrictions, which is exactly what makes the selection possible.

A second pitfall is to claim that the infinite theorem itself supplies a finite numerical bound. The theorem guarantees an infinite monochromatic set after a coloring of all pairs has been constructed. The contradiction proves that some finite Ramsey threshold exists, but this reasoning does not calculate that threshold. Numerical bounds require additional arguments.