Exact Boundary Values R(2,t)

The Boundary Case in Ramsey Theory

A Ramsey number records how many vertices force a monochromatic pattern, regardless of how the edges are colored. The boundary value \(R(2,t)\) is especially direct: a red copy of \(K_2\) is just one red edge, while the other target is a blue complete graph on \(t\) vertices. The exact value comes from a simple dichotomy on \(K_t\), together with a coloring on fewer vertices that shows the threshold cannot be smaller.

All graphs in this tutorial are finite and simple. For an integer \(n\ge 1\), the complete graph \(K_n\) has \(n\) vertices and an edge between every pair of distinct vertices. A red-blue edge-coloring assigns exactly one of the two colors to each edge. A monochromatic \(K_s\) is a set of \(s\) vertices whose every pair is joined by an edge of the same color. In particular, a red \(K_2\) is exactly a red edge.

To determine this least integer, two claims are needed. First, the desired outcome must occur in every coloring at some order. Second, it must fail for every smaller order. These are separate parts of an exact-value proof: the first gives an upper bound, and the second certifies that the upper bound is sharp.

Why \(K_t\) Always Forces One of the Two Outcomes

Proof. Fix an integer \(t\ge2\) and a red-blue coloring of \(K_t\). If at least one edge is red, that edge is a red \(K_2\), so the first outcome occurs. If no edge is red, then each edge must be blue, because every edge receives exactly one of the two colors. Therefore all edges among the \(t\) vertices are blue, and those vertices form a blue \(K_t\). The two cases cover every coloring, so the claim holds. \(\square\)

This argument does not require counting edges or locating a particular blue clique inside a larger graph: when there is no red edge, the entire \(K_t\) is blue. The number of edges in \(K_t\) is \(\binom{t}{2}=t(t-1)/2\); the proof says that either at least one of these edges is red, or all \(t(t-1)/2\) edges are blue.

Why Fewer Than \(t\) Vertices Do Not Suffice

Now consider an order \(n<t\). Color every edge of \(K_n\) blue. There is no red \(K_2\), since there are no red edges. There is also no blue \(K_t\): a set of \(t\) distinct vertices cannot be chosen from a vertex set of size \(n<t\). This argument applies to every positive integer \(n<t\), including \(n=1\), where there are no edges to color and neither target can occur.

Proof. The first theorem shows that the defining property of \(R(2,t)\) holds when \(n=t\), so \(R(2,t)\le t\). For each positive integer \(n<t\), the coloring of \(K_n\) in which every edge is blue has no red \(K_2\) and no blue \(K_t\). Thus the defining property fails for every positive \(n<t\), so \(R(2,t)\ge t\). Combining the two inequalities gives \(R(2,t)=t\). \(\square\)

The lower-bound construction is deliberately uniform: it works at every smaller order, not just at \(t-1\). Equivalently, the all-blue coloring of \(K_{t-1}\) already shows the threshold cannot be at most \(t-1\), because restricting that coloring to any smaller complete graph gives the same failure there.

Worked Examples at Small Values

Common Pitfall: Confusing the Lower-Bound Coloring with a Blue Target

A frequent off-by-one error is to say that the all-blue coloring of \(K_{t-1}\) contains a blue \(K_t\). It does not: a clique of order \(t\) requires \(t\) distinct vertices, and \(K_{t-1}\) has only \(t-1\). The all-blue coloring is instead a certificate that the Ramsey property fails below \(t\): it avoids a red \(K_2\), and its vertex set is too small to contain a blue \(K_t\).

For a concrete check, let \(t=4\). The graph \(K_3\) has \(3(3-1)/2=3\) edges; coloring all three blue gives no red \(K_2\). Its largest possible vertex set has size \(3\), so it cannot contain a blue \(K_4\). At order \(4\), there are \(4(4-1)/2=6\) edges: if any is red it is the required red \(K_2\), and if none is red all six are blue and form a blue \(K_4\). The change from three vertices to four is exactly the threshold.

The value \(R(2,t)=t\) is a useful boundary case because its upper-bound argument needs no recurrence or elaborate structure. Its exactness still depends on checking both directions: the dichotomy proves that \(t\) vertices suffice, while the all-blue coloring proves that every smaller order fails. This same separation between a forcing argument and a counterexample below the proposed threshold is central to exact Ramsey-number proofs.