Off-Diagonal Bounds for R(3,t)

From a Neighborhood Recurrence to a Quadratic Bound

A Ramsey number is the least order at which every red-blue coloring of a complete graph contains one of two specified monochromatic cliques. When one target is a triangle and the other is a clique whose order depends on \(t\), a vertex-neighborhood argument gives a recurrence. Iterating that recurrence produces a quadratic upper bound for \(R(3,t)\). The estimate is useful even when it is not sharp: it gives an explicit order at which the desired monochromatic clique is guaranteed.

For positive integers \(a,b\), let \(R(a,b)\) denote the least integer \(n\) such that every red-blue coloring of the edges of \(K_n\) contains either a red \(K_a\) or a blue \(K_b\). Here a monochromatic \(K_a\) means a set of \(a\) vertices whose every pair is joined by a red edge; a blue \(K_b\) is defined in the same way using blue edges. The existence of these finite Ramsey numbers is established in the earlier material on Ramsey theory.

We use the standard convention that \(K_n\) has vertex set \(\{1,\ldots,n\}\) and edge set consisting of all unordered pairs of distinct vertices. A red or blue coloring assigns one of those two colors to every edge. If a coloring has the Ramsey property at order \(n\), it also has it at every larger order: restrict any coloring of the larger complete graph to \(n\) vertices. Thus the least order in the definition is a threshold, and failure at every smaller order follows from its being least.

The Boundary Values and the Recurrence

The recurrence needs two simple boundary facts. For \(t\ge2\), the value \(R(2,t)\) is \(t\). Also \(R(3,2)=3\). These provide the terms from which we will build the bound.

Proof. On \(K_t\), if there is a red edge, its two endpoints form a red \(K_2\). If there is no red edge, every edge is blue, so all \(t\) vertices form a blue \(K_t\). Therefore \(R(2,t)\le t\). For each integer \(n<t\), color every edge of \(K_n\) blue. This coloring has no red \(K_2\), and it has no blue \(K_t\) because it has fewer than \(t\) vertices. Hence no such \(n\) has the Ramsey property, proving \(R(2,t)=t\). For \(R(3,2)\), any coloring of \(K_3\) either has a blue edge, which is a blue \(K_2\), or has all three edges red, which is a red \(K_3\). On \(K_2\), an all-red coloring has neither a red \(K_3\) nor a blue \(K_2\). Thus \(R(3,2)=3\). \(\square\)

Proof. Write \(A=R(2,t)\) and \(B=R(3,t-1)\), and consider any red-blue coloring of \(K_{A+B}\), whose vertices are \(\{1,\ldots,A+B\}\) and whose edges are all pairs of distinct vertices. Choose a vertex \(v\). Its \(A+B-1\) neighbors split into the set joined to \(v\) by red edges and the set joined to \(v\) by blue edges. If the red-neighbor set has at least \(A\) vertices, the definition of \(R(2,t)\), applied to the coloring among any \(A\) of them, gives either a red \(K_2\) or a blue \(K_t\). In the first case, adding \(v\), which is red-adjacent to both endpoints, gives a red \(K_3\); in the second case, the blue \(K_t\) already gives the target. If instead the blue-neighbor set has at least \(B\) vertices, apply the definition of \(R(3,t-1)\) among \(B\) of them. A red \(K_3\) is already a target, while a blue \(K_{t-1}\), together with \(v\), forms a blue \(K_t\).

It remains to verify that at least one of those two size conditions holds. If the red-neighbor set had at most \(A-1\) vertices and the blue-neighbor set at most \(B-1\), their combined size would be at most \(A+B-2\). But they partition the \(A+B-1\) neighbors of \(v\), which is impossible. Thus every coloring of \(K_{A+B}\) has a red \(K_3\) or a blue \(K_t\), and the definition of \(R(3,t)\) gives the stated inequality. \(\square\)

Iterating the Recurrence

Substitute the boundary value \(R(2,t)=t\) into the recurrence. For each \(t\ge3\), this gives \(R(3,t)\le t+R(3,t-1)\). Repeated substitution adds the successive integers \(3,4,\ldots,t\) to the initial value \(R(3,2)=3\).

Proof. We use induction on \(t\). At \(t=2\), the boundary value gives \(R(3,2)=3=2\cdot3/2\). Now let \(t\ge3\), and suppose \(R(3,t-1)\le (t-1)t/2\). The recurrence and the boundary value \(R(2,t)=t\) imply $$ R(3,t)\le t+R(3,t-1)\le t+\frac{(t-1)t}{2} =\frac{2t+t^2-t}{2}=\frac{t(t+1)}{2}. $$ This proves the claim for \(t\), completing the induction. \(\square\)

The same computation can be written as a sum. Starting with \(R(3,2)=3\), apply the recurrence once for each integer from \(3\) through \(t\): $$ R(3,t)\le 3+\sum_{j=3}^{t}j =3+\left(\frac{t(t+1)}{2}-3\right) =\frac{t(t+1)}{2}. $$ The subtraction of \(3\) removes the first two terms \(1+2\) from the full sum \(1+\cdots+t\); the initial boundary value then contributes \(3\).

Worked Estimates

Interpreting the Bound and Avoiding a Common Error

The quadratic estimate is an upper bound on a threshold. Since \(R(3,t)\le t(t+1)/2\), every coloring at the displayed order has the required monochromatic clique. It does not say that every coloring at that order needs all those vertices, nor that no smaller order works. Because \(R(3,t)\) is the least order with the Ramsey property, every smaller order does have a coloring avoiding both target cliques; but the quadratic calculation does not identify that least order unless its bound happens to be exact.

A common arithmetic mistake is to stop the sum at \(t\) and forget the starting value \(R(3,2)=3\). For \(t=5\), this can lead to the incorrect estimate \(5+4+3=12\), as though the recurrence had ended after adding \(3\). But after applying the recurrence at \(t=3\), the remaining term is still \(R(3,2)=3\). The complete calculation is \(5+4+3+3=15\), not \(12\). Equivalently, the sum of recurrence increments is \(3+4+5=12\), and the initial boundary value contributes another \(3\).

The order of the targets also matters when using neighborhoods: the red-neighbor case invokes \(R(2,t)\), because a red pair there combines with the chosen vertex to make a red triangle. The blue-neighbor case invokes \(R(3,t-1)\), because the chosen vertex completes a blue clique. Keeping these roles distinct is what makes the recurrence valid.