A Workshop on Mixed Ramsey Bounds

Building Bounds from Different Sources

A mixed Ramsey number concerns two possibly different clique sizes. In a complete graph whose edges are colored red or blue, $R(s,t)$ is the least number of vertices that guarantees either a red clique of size $s$ or a blue clique of size $t$. The parameters need not be equal, so useful bounds often come from combining information about several different pairs.

There are two complementary tasks. To prove an upper bound, show that every coloring on a certain number of vertices contains one of the required cliques. To prove a lower bound, exhibit a coloring on some number of vertices that contains neither. Together these give an interval for the unknown value. Symmetry, monotonicity and the recurrence let us transfer and combine bounds; explicit colorings supply witnesses for lower bounds.

Definition: For positive integers $s,t$, $R(s,t)$ is the least integer $n$ such that every red-blue coloring of the edges of the complete graph $K_n$ contains either a red $K_s$ or a blue $K_t$. A set of vertices forms a red (respectively, blue) $K_j$ when every edge between its vertices is red (respectively, blue). A coloring on $N$ vertices with neither target clique proves $R(s,t)>N$.

The finite existence of these numbers is part of the earlier material on Ramsey existence. The convention on colors matters: throughout, the first parameter refers to the red clique and the second to the blue clique.

Three Rules for Comparing Ramsey Numbers

Proposition: For positive integers $s,t$, the following hold:

Symmetry: $R(s,t)=R(t,s)$.
Monotonicity: if $s\le s'$ and $t\le t'$, then $R(s,t)\le R(s',t')$.
Boundary values: $R(1,t)=R(t,1)=1$, and $R(2,t)=R(t,2)=t$ for $t\ge2$.

Proof. Swapping the names red and blue in any coloring exchanges the two targets. Thus the least order guaranteeing a red $K_s$ or blue $K_t$ is also the least order guaranteeing a red $K_t$ or blue $K_s$, proving symmetry. If a coloring contains a red $K_{s'}$ with $s'\ge s$, any $s$ of its vertices form a red $K_s$; the corresponding statement holds for blue cliques. Therefore a guarantee for the larger targets also guarantees the smaller ones, which proves monotonicity. A single vertex is a $K_1$, so $R(1,t)=R(t,1)=1$. For $t\ge2$, every coloring of $K_t$ either has a red edge, which is a red $K_2$, or has no red edge, in which case all its edges are blue and it is a blue $K_t$. On $t-1$ vertices, coloring every edge blue gives neither a red $K_2$ nor a blue $K_t$. Hence $R(2,t)=t$; symmetry gives $R(t,2)=t$. $\square$

The recurrence is the main way to turn known smaller values into a new upper bound. It gives an upper bound, not automatically an equality.

Theorem (Ramsey recurrence): For integers $s,t\ge2$, $$ R(s,t)\le R(s-1,t)+R(s,t-1). $$

Proof. Write $a=R(s-1,t)$ and $b=R(s,t-1)$, and consider an arbitrary red-blue coloring of $K_{a+b}$. Choose a vertex $v$. Its $a+b-1$ other vertices split into red neighbors and blue neighbors. If there are at least $a$ red neighbors, choose $a$ of them. The coloring they induce contains a red $K_{s-1}$ or a blue $K_t$, by the definition of $a$. A blue $K_t$ already gives the required target; a red $K_{s-1}$, together with $v$, gives a red $K_s$. If there are fewer than $a$ red neighbors, there are at most $a-1$ of them, so at least $(a+b-1)-(a-1)=b$ vertices are blue neighbors of $v$. Choose $b$ of these. Their coloring contains a red $K_s$ or a blue $K_{t-1}$, by the definition of $b$. The red target is already present; the blue $K_{t-1}$, together with $v$, gives a blue $K_t$. Thus every coloring of $K_{a+b}$ has a target clique, proving the inequality. $\square$

When applying the recurrence, the boundary values and symmetry help keep the calculation manageable. The values on its right-hand side must themselves be exact or valid upper bounds: substituting upper bounds still gives a valid upper bound for the left-hand side.

Worked Example: An Upper Bound for R(3,5)

Use the recurrence and the known exact value $R(3,4)=9$ to bound $R(3,5)$. The parameters $3$ and $5$ are both at least $2$, so the recurrence applies:

R(3,5)\le R(2,5)+R(3,4).

The boundary value gives $R(2,5)=5$, and the supplied exact small value is $R(3,4)=9$. Substitution gives $R(3,5)\le 5+9=14$.

Check: the recurrence has reduced the pair $(3,5)$ to $(2,5)$ and $(3,4)$, and both terms have been evaluated. The result is an upper bound of $14$; this calculation alone does not show that a coloring avoiding both targets exists on $13$ vertices.

Colorings as Lower-Bound Witnesses

For a lower bound, the direction of the argument reverses: one particular coloring is enough. If a coloring on $N$ vertices has no red $K_s$ and no blue $K_t$, then the defining guarantee fails at order $N$. Consequently $R(s,t)>N$, or, since it is an integer, $R(s,t)\ge N+1$.

It is useful to describe a coloring by specifying its red graph $G$: its vertex set is the vertex set of the complete graph, its red edges are $E(G)$, and every other edge is blue. A red clique is then a clique in $G$, while a blue clique is an independent set in $G$, meaning a vertex set containing no edge of $G$. This translation makes it possible to check both forbidden targets directly.

Worked Example: A Lower Bound for R(4,5)

Let the vertex set be $\{1,2,3,4,5,6,7,8,9\}$. Color the edges $12,23,34,45,56,67,78,89,91$ red and every other edge blue. Thus the red graph is the cycle $C_9$. We check each target separately.

The red graph has no triangle: the two neighbors of any vertex on this cycle are not adjacent to each other. Any clique of size at least $3$ contains a triangle, so this coloring has no red $K_4$.

A blue clique is an independent set in the red cycle. In any independent set of $C_9$, the vertex immediately following each selected vertex around the cycle is unselected. These following vertices are distinct, so if the independent set has $q$ vertices, then $q$ selected vertices and $q$ distinct unselected vertices fit among the $9$ cycle vertices. Hence $2q\le9$, which gives $q\le4$. The set $\{1,3,5,7\}$ is independent, so the maximum independent-set size is exactly $4$. In particular, there is no blue $K_5$.

Check: this is a coloring on $9$ vertices with neither a red $K_4$ nor a blue $K_5$. Therefore $R(4,5)>9$, and integrality gives $R(4,5)\ge10$. The construction verifies the lower bound directly rather than inferring it from an upper-bound recurrence.

Combining the Pieces for a Mixed Pair

Worked Example: An Interval for R(4,5)

We now combine recurrence calculations with the coloring witness. For an upper bound, first apply the recurrence to $(4,4)$. Using symmetry and the exact value $R(3,4)=9$, we obtain $R(4,4)\le R(3,4)+R(4,3)=9+9=18$.

For $(4,5)$, the recurrence gives $R(4,5)\le R(3,5)+R(4,4)$. The first worked calculation gives $R(3,5)\le14$, and the calculation just made gives $R(4,4)\le18$. Therefore $R(4,5)\le14+18=32$.

The cycle coloring gives $R(4,5)\ge10$. Taken together, the bounds are $10\le R(4,5)\le32$.

Check: the upper-bound calculation uses only inequalities in the correct direction: $R(3,5)\le14$ and $R(4,4)\le18$, so their sum bounds $R(4,5)$ from above. The lower-bound calculation is independent: it comes from a coloring on $9$ vertices, so it forces the Ramsey number to be at least $10$. These two arguments establish an interval, not an exact value.

The same ingredients can be reused for another pair. For example, symmetry and the recurrence give $R(5,5)\le R(4,5)+R(5,4)=2R(4,5)$. Since the preceding upper bound is $R(4,5)\le32$, this yields $R(5,5)\le2\cdot32=64$. For a lower bound, the $C_9$ coloring already checked has no red $K_4$ and no blue $K_5$; therefore it also has no red $K_5$ or blue $K_5$. It follows that $R(5,5)\ge10$. Thus these arguments give $10\le R(5,5)\le64$. The lower bound is valid but deliberately modest: the construction need only be checked against the requested targets, not optimized to make the interval narrow.

Common Pitfalls and a Practical Workflow

Do not turn the recurrence into an equality. From the calculation above, $R(4,5)\le32$ follows. Writing $R(4,5)=32$ would be an error: the recurrence proves that $32$ vertices suffice, but it does not rule out a smaller sufficient number. An exact value needs a matching lower bound, which would require a coloring witness of order $31$ as well as the upper-bound argument.

Keep track of what a witness proves. The $C_9$ example proves $R(4,5)\ge10$, because it avoids both targets on $9$ vertices. It does not prove $R(4,5)=10$: that would also require proving that every coloring on $10$ vertices contains a red $K_4$ or a blue $K_5$.

For a new mixed pair, a reliable sequence of steps is:

Use symmetry to put the parameters in a convenient order.
Use monotonicity or exact values to identify useful smaller pairs.
Apply the recurrence only when its parameters are at least $2$, and evaluate each term or replace it with a justified bound.
For a lower bound, specify the whole coloring and check both forbidden clique types.
State the resulting interval and do not call it an exact value unless the upper and lower bounds meet.

This approach is useful precisely because upper and lower bounds require different kinds of evidence. Recurrence calculations control every coloring; an explicit witness demonstrates one coloring that avoids the targets. Combining the two gives a transparent account of what is known and what remains unproved about a mixed Ramsey number.

Check Your Understanding

For each question, distinguish carefully between an upper-bound calculation and a lower-bound witness.

Use the recurrence and the boundary value $R(2,6)=6$ to obtain an upper bound for $R(3,6)$, given $R(3,5)\le14$.
Explain why a coloring on $12$ vertices avoiding a red $K_4$ and a blue $K_6$ proves $R(4,6)\ge13$.
Use symmetry and the recurrence to express an upper bound for $R(5,5)$ in terms of $R(4,5)$.
Why does $R(4,5)\le32$ not imply that a coloring avoiding both targets exists on $31$ vertices?
In a red-graph description of a two-coloring, what graph property corresponds to a blue clique?