The Recurrence and Its Off-by-One
In a finite edge-coloring of a complete graph, fix a vertex and group its neighbors by the colors of the edges joining them to that vertex. A sufficiently large group is itself a complete graph to which a smaller Ramsey number applies. Counting these groups gives the multicolor Ramsey recurrence. The count is sensitive to one vertex: the valid standard bound has a leading \(2\), not a leading \(1\).
When a target is decremented from \(2\) to \(1\), this convention applies directly. In the recurrence proof, the corresponding smaller Ramsey number is then \(1\), and its contribution to the sum is \(1-1=0\).
The recurrence with \(1\) in place of the leading \(2\) is false in general. For example, it would give \(R(3,3)\le5\), whereas \(R(3,3)=6\). We will verify that example below. The extra vertex in the valid bound is exactly what makes the neighbor-counting argument force one color class to reach the size of its smaller Ramsey number.
Why the Neighbor Count Works
Write \(R_i=R(s_1,\ldots,s_i-1,\ldots,s_m)\). The number \(R_i\) is the threshold for a coloring on a set of \(R_i\) vertices. Thus the vertex argument needs a color class of at least \(R_i\) neighbors, not merely \(R_i-1\). This is the key point in the count.
Proof. Set \(N=2+\sum_{i=1}^m(R_i-1)\), and consider any \(m\)-coloring of the edges of \(K_N\). Fix a vertex \(v\). For each \(i\), let \(A_i\) be the set of vertices joined to \(v\) by a color-\(i\) edge. The sets \(A_1,\ldots,A_m\) partition the other \(N-1\) vertices, so $$ \sum_{i=1}^m |A_i|=N-1=1+\sum_{i=1}^m(R_i-1). $$ If \(|A_i|\le R_i-1\) for every \(i\), summing those inequalities would give \(\sum_i|A_i|\le\sum_i(R_i-1)\), contradicting the displayed equality. Therefore some \(i\) has \(|A_i|\ge R_i\). Choose \(R_i\) vertices from \(A_i\). Their induced complete graph, with its inherited edge-coloring, contains either a color-\(i\) clique of order \(s_i-1\), or a color-\(j\) clique of order \(s_j\) for some \(j\ne i\), by the definition of \(R_i\). In the first case, all its vertices are joined to \(v\) in color \(i\), so adjoining \(v\) gives a color-\(i\) clique of order \(s_i\). In the second case the required clique is already present. Thus every coloring of \(K_N\) has a required monochromatic clique, proving the bound. \(\square\)
If \(s_i=2\), then \(R_i=1\) by the size-one convention. The argument still applies: \(|A_i|\ge R_i=1\) gives a vertex joined to \(v\) in color \(i\), and these two vertices form the required color-\(i\) \(K_2\). No step requires a Ramsey number with target zero.
Worked Applications
Worked Example: Checking the Two-Color Boundary Case
First calculate \(R(2,3)\). Any coloring of \(K_3\) either has a color-1 edge, which is a color-1 \(K_2\), or has no color-1 edge, in which case all three edges are color 2 and form a color-2 \(K_3\). Therefore \(R(2,3)\le3\). On \(K_2\), color its only edge color 2: there is no color-1 \(K_2\) and no color-2 \(K_3\). Thus \(R(2,3)>2\), so \(R(2,3)=3\).
Now apply the recurrence to \(R(3,3)\). Each decremented term is \(R(2,3)=3\) or \(R(3,2)=3\), where the second equality follows by interchanging the two colors. Hence $$ R(3,3)\le 2+(3-1)+(3-1)=2+2+2=6. $$
To check the lower bound, color the edges of \(K_5\) with vertices \(\{1,2,3,4,5\}\). Give color 1 to \(12,23,34,45,51\), and color 2 to \(13,14,24,25,35\). The color-1 edges form the cycle \(1,2,3,4,5,1\); the color-2 edges form the cycle \(1,3,5,2,4,1\). A cycle of length 5 contains no triangle, so neither color has a monochromatic \(K_3\). Therefore \(R(3,3)>5\), and the upper and lower bounds give \(R(3,3)=6\). In particular, the proposed bound with leading \(1\) would say \(R(3,3)\le1+2+2=5\), contradicting this verified value.
Worked Example: Three Colors with Target Two
Consider \(R(2,2,2)\). Decrementing any one target gives \(R(1,2,2)=1\), so the recurrence gives $$ R(2,2,2)\le 2+(1-1)+(1-1)+(1-1)=2+0+0+0=2. $$
For the reverse bound, \(K_1\) has no edges and hence has no monochromatic \(K_2\), so \(R(2,2,2)>1\). In \(K_2\), the single edge receives one of the three colors and is a monochromatic \(K_2\) in that color. Thus \(R(2,2,2)\le2\), and together the bounds give \(R(2,2,2)=2\). This example also shows why a zero contribution from a decremented term is harmless: the vertex argument can still detect a color-\(i\) edge.
Worked Example: What a Target of One Means
Under the size-one convention, \(R(1,5,3)=1\). Indeed, in any coloring with at least one vertex, that vertex alone is a color-1 \(K_1\). The least positive order with the Ramsey property is therefore \(1\).
Do not confuse this with \(R(2,5,3)\). Here none of the targets is one. A coloring avoiding a color-1 \(K_2\) must have no color-1 edges at all; its remaining edges are colored with colors 2 and 3. Conversely, any coloring using only colors 2 and 3 that avoids a color-2 \(K_5\) and a color-3 \(K_3\) also avoids all three target cliques when regarded as a three-coloring. Thus the condition for \(R(2,5,3)\) reduces to the two-color condition for \(R(5,3)\). The size-one convention applies to the decremented term \(R(1,5,3)\), not to \(R(2,5,3)\).
In the recurrence for \(R(2,5,3)\), the term from decrementing the first target is \(R(1,5,3)=1\), whose contribution is \(1-1=0\). The other two terms are \(R(2,4,3)\) and \(R(2,5,2)\). Substituting into the valid recurrence gives $$ R(2,5,3)\le 2+(1-1)+(R(2,4,3)-1)+(R(2,5,2)-1). $$ The zero contribution is a consequence of the boundary convention; it does not make the original target \(2\) a size-one case.
Using the Recurrence Carefully
The recurrence is an upper-bound tool. Each term on the right has one target reduced by one, and all the terms must be included, even when a decrement reaches one. The sum counts the maximum allowed neighbor-class sizes if every class falls short of its Ramsey threshold; the additional \(1\) among the \(N-1\) neighbors makes that simultaneous shortfall impossible.
Common mistake: losing the extra vertex. A tempting count is to set \(N=1+\sum_i(R_i-1)\) and say that the \(N-1\) neighbors cannot all lie in classes of size at most \(R_i-1\). But in that case $$ N-1=\sum_i(R_i-1), $$ so the classes can, in principle, have exactly those sizes. There is no contradiction. For \(R(3,3)\), the arithmetic makes the error concrete: \(1+(3-1)+(3-1)=5\), but the explicit coloring of \(K_5\) above has no monochromatic triangle. With \(N=2+\sum_i(R_i-1)\), instead, \(N-1=1+\sum_i(R_i-1)\), which is strictly larger than the sum of the proposed class-size limits.
The proof also clarifies how to handle the boundary consistently. If a target is \(2\), its decrement is \(1\), the smaller Ramsey number is \(1\), and a nonempty neighbor class of that color immediately supplies the desired edge together with the chosen vertex. If an original target is already \(1\), the Ramsey property holds at order one by definition, so there is no need to apply the recurrence proof.
Check Your Understanding
Use the definitions and the neighbor-class count to answer the following.
- For \(R(2,4)\), what is the term obtained by decrementing the first target, and why does its contribution to the recurrence sum equal zero?
- In the recurrence proof, why does a neighbor class need size at least \(R_i\), rather than merely \(R_i-1\)?
- Verify directly that a color-1 edge in a coloring of \(K_3\) gives the target for \(R(2,3)\), and explain what happens if there is no such edge.
- Why does the explicit coloring of \(K_5\) in the first worked example disprove a bound of \(1+\sum_i(R_i-1)\) for \(R(3,3)\)?
- Explain why \(R(1,5,3)=1\) but the size-one convention does not apply directly to \(R(2,5,3)\).