Computing Upper Bounds from the Recurrence

From the Recurrence to Numerical Bounds

The Ramsey recurrence gives a systematic way to produce numerical upper bounds. Its calculations are short once the boundary values are set, but it is important to keep track of what the result means: a recurrence-derived upper bound guarantees that a monochromatic clique appears by a certain order; by itself, it does not show that this order is the smallest one that works.

Throughout, a red-blue edge-colouring of a complete graph assigns one of two colours to each edge. A red \(K_s\) is a set of \(s\) vertices whose every joining edge is red; a blue \(K_t\) is defined in the same way.

The recurrence is used when \(s,t\ge2\). In practice, we calculate a numerical table of upper bounds rather than assume that the recurrence gives the exact Ramsey numbers. To make this distinction explicit, write \(U(s,t)\) for the bound obtained by the recurrence.

The recurrence for \(R\) is the neighborhood recurrence. Its proof is included here to make clear why the numerical procedure supplies a valid upper bound. The value at \((s,t)\) depends on two entries with smaller parameter sum, so the boundary values and previously computed entries are enough to fill the table.

Why the Recurrence Gives an Upper Bound

Proof. Let \(a=R(s-1,t)\) and \(b=R(s,t-1)\), where \(s,t\ge2\). Consider any red-blue colouring of \(K_{a+b}\), and choose a vertex \(v\). There are \(a+b-1\) edges incident with \(v\). If fewer than \(a\) are red and fewer than \(b\) are blue, there are at most \((a-1)+(b-1)=a+b-2\) such edges, contradicting the actual count \(a+b-1\). Thus \(v\) has at least \(a\) red neighbours or at least \(b\) blue neighbours. In the first case, the subgraph on \(a\) of its red neighbours contains a red \(K_{s-1}\) or a blue \(K_t\), by the definition of \(a\). A red \(K_{s-1}\) together with \(v\) is a red \(K_s\); a blue \(K_t\) already gives the required outcome. In the second case, the subgraph on \(b\) of its blue neighbours contains a red \(K_s\) or a blue \(K_{t-1}\), by the definition of \(b\). The red clique already suffices, and a blue \(K_{t-1}\) together with \(v\) is a blue \(K_t\). Therefore every colouring of \(K_{a+b}\) has the required clique, proving \(R(s,t)\le a+b\).

It follows that \(R(s,t)\le U(s,t)\) for every pair of positive integers. On the boundary, \(R(1,t)=U(1,t)=1\) and \(R(t,1)=U(t,1)=1\). For \(s,t\ge2\), assume the claim holds for parameter pairs with smaller sum. The recurrence just proved gives \(R(s,t)\le R(s-1,t)+R(s,t-1)\le U(s-1,t)+U(s,t-1)=U(s,t)\). This completes the induction. \(\square\)

Worked Recurrence Calculations

Reading the Table Correctly

The recurrence values form a table in which each interior entry is the sum of the entry immediately above it and the entry immediately to its left. The boundary entries are all \(1\). For example, the calculation for \(U(3,4)\) uses \(U(2,4)\) and \(U(3,3)\); it does not use \(U(2,3)\) directly except through the earlier calculations that produced those entries.

The symmetry \(U(s,t)=U(t,s)\) follows from the recurrence: the boundary values are symmetric, and swapping the two parameters swaps the two summands. Equivalently, exchanging the names red and blue in a colouring exchanges the roles of \(s\) and \(t\). Symmetry is useful for reducing repeated calculations, but it does not alter the meaning of an upper bound.

For positive parameters, the Pascal recurrence also gives the familiar closed form for these recurrence bounds: \(U(s,t)=\binom{s+t-2}{s-1}\). This is the binomial upper bound proved by Pascal induction. The worked examples use it as an independent arithmetic check, while the recurrence itself shows how the bound is assembled from smaller parameter pairs.

Upper Bounds Are Not Exact Values

An upper bound \(R(s,t)\le N\) says that every red-blue colouring of \(K_N\) has a red \(K_s\) or a blue \(K_t\). It does not rule out the same guarantee holding already at a smaller order. By definition, to establish \(R(s,t)=N\), one must prove both that every colouring of \(K_N\) has the required clique and that at least one colouring of \(K_{N-1}\) avoids both target cliques. The recurrence supplies the first kind of statement at its computed bound, but it does not automatically supply the second.

This distinction matters even when the arithmetic is flawless. For instance, the calculation \(U(3,4)=10\) certifies \(R(3,4)\le10\); it does not establish \(R(3,4)=10\). A coloring that avoids the target cliques at some smaller order would be needed to show a matching lower bound. The same logical distinction applies to \(U(4,4)=20\) and \(U(3,5)=15\).

Common Pitfall: Treating the Recurrence as Equality

A tempting but invalid step is to write \(R(3,4)=R(2,4)+R(3,3)\) simply because the recurrence has those terms. The proved statement is an inequality. Even if the numerical upper-bound entries add to \(4+6=10\), this establishes only \(R(3,4)\le10\). Equality would require an additional lower-bound argument showing that some colouring of \(K_9\) avoids both a red \(K_3\) and a blue \(K_4\). Without that argument, the conclusion \(R(3,4)=10\) does not follow.

A second arithmetic error is to use the wrong boundary: taking \(U(1,t)=0\) would make \(U(2,2)=0+0=0\), contradicting the definition, since a one-vertex clique already meets a target of order \(1\). The correct boundary is \(1\), and every interior value is computed from the two preceding entries.