Symmetry and Monotonicity Laws for Ramsey Numbers

Ramsey Numbers and Their Forcing Property

A two-colour Ramsey number records how many vertices guarantee a monochromatic clique of one of two specified sizes. Its symmetry and monotonicity come directly from the definition: swapping the names of the colours exchanges the targets, while a clique contains smaller cliques of the same colour. These observations give useful comparisons without computing the numbers themselves.

Throughout, $s,t$ are integers at least $2$. A red-blue colouring of a complete graph assigns one of the two colours to every edge. A monochromatic $K_s$ is a set of $s$ vertices for which every pair is joined by an edge of the same colour; it is a red $K_s$ or a blue $K_s$ according to that colour. The finite Ramsey theorem, established in the earlier material on finite Ramsey numbers, guarantees that the least integer in the definition below exists.

Definition: The two-colour Ramsey number $R(s,t)$ is the least positive integer $n$ such that every red-blue colouring of the edges of $K_n$ contains either a red $K_s$ or a blue $K_t$. A colouring with neither such clique is said to avoid the pair $(s,t)$.

The order of the targets specifies which colour is associated with which size: the first target is red and the second is blue. The symmetry law says this order does not affect the number. The monotonicity laws compare different target sizes. They are non-strict inequalities: they say that enlarging a target cannot decrease the Ramsey number, but do not say that it must increase.

The Symmetry Law

Theorem: For all integers $s,t\ge2$, $R(s,t)=R(t,s)$.

Proof. Fix any positive integer $n$. Take a red-blue colouring of $K_n$ and interchange the colour of every edge. This operation is reversible: applying it twice restores the original colouring. In the original colouring, a red $K_s$ becomes a blue $K_s$ after the interchange, and a blue $K_t$ becomes a red $K_t$. Thus every colouring of $K_n$ contains a red $K_s$ or a blue $K_t$ if and only if every colouring of $K_n$ contains a red $K_t$ or a blue $K_s$. The sets of positive integers $n$ with these two forcing properties are therefore identical. Their least elements are identical, which gives $R(s,t)=R(t,s)$. $\square$

The reversible colour exchange matters: it establishes equivalence of the two forcing properties for every $n$, not just a one-way implication for a particular colouring.

Worked Example: Exchanging Colours in a Complete Graph

Let $G=K_4$, with vertex set $V=\{1,2,3,4\}$. Colour the edges $12,23,34,14$ red and $13,24$ blue. These are all six edges: $|E(K_4)|=4\cdot3/2=6$, and the two colour classes have sizes $4$ and $2$.

Check each of the four triples. On $\{1,2,3\}$, edges $12,23$ are red and $13$ is blue. On $\{1,2,4\}$, edges $12,14$ are red and $24$ is blue. On $\{1,3,4\}$, edges $14,34$ are red and $13$ is blue. On $\{2,3,4\}$, edges $23,34$ are red and $24$ is blue. Each triple has both colours, so none is a monochromatic triangle.

After interchanging the colours, the four edges $12,23,34,14$ are blue and $13,24$ are red. The same four triple checks still show that no triple is monochromatic. In particular, the property “avoids a red triangle and a blue triangle” is preserved here. In general, colour interchange also exchanges unequal targets, as in the theorem.

Check: before and after the interchange there are $4+2=6$ edges, and every listed edge has exactly one colour. Each of the four triples has two edges of one colour and one of the other, so the absence of a monochromatic triangle is verified directly.

Monotonicity in the Targets

Theorem: For all integers $s,t\ge2$, $$ R(s,t)\le R(s+1,t) \qquad\text{and}\qquad R(s,t)\le R(s,t+1). $$

Proof. Set $n=R(s+1,t)$, and consider any red-blue colouring of $K_n$. By the definition of $R(s+1,t)$, this colouring contains a red $K_{s+1}$ or a blue $K_t$. In the second case it already contains one of the cliques required for the pair $(s,t)$. In the first case, choose any $s$ vertices from the red $K_{s+1}$. Every pair among those $s$ vertices is still joined by a red edge, so they form a red $K_s$. Therefore every colouring of $K_n$ contains a red $K_s$ or a blue $K_t$. By the least-integer definition, $R(s,t)\le n=R(s+1,t)$.

For the other inequality, set $n=R(s,t+1)$. Every colouring of $K_n$ contains a red $K_s$ or a blue $K_{t+1}$. A red $K_s$ is already sufficient; from a blue $K_{t+1}$, choosing any $t$ vertices gives a blue $K_t$. Thus $n$ forces the pair $(s,t)$, and $R(s,t)\le R(s,t+1)$. Both arguments use only the definition of a monochromatic clique and the defining forcing property. $\square$

The inequalities also compare targets that differ by more than one. Repeated application gives $R(s,t)\le R(s+a,t+b)$ for any nonnegative integers $a,b$. If $a>0$, apply the first inequality successively $a$ times; if $b>0$, apply the second inequality successively $b$ times. Transitivity of $\le$ then gives the stated comparison. This says nothing about whether any of these inequalities is strict.

Worked Example: Restricting a Red Clique

Let $G=K_5$, with vertex set $V=\{1,2,3,4,5\}$. Colour $12,13,14,23,24,34$ red and $15,25,35,45$ blue. The red edges are exactly all pairs within $\{1,2,3,4\}$; the blue edges are exactly all pairs joining $5$ to one of $1,2,3,4$.

There are $6+4=10$ edges, which agrees with $|E(K_5)|=5\cdot4/2=10$. The vertices $\{1,2,3,4\}$ form a red $K_4$. Restrict to $\{1,2,3\}$: its three edges are $12,13,23$, all red, so it is a red $K_3$. Another restriction, to $\{1,2,4\}$, has edges $12,14,24$, also all red.

This concrete restriction is the step used in the first monotonicity proof: a red clique of size $s+1$ supplies a red clique of size $s$. For contrast, the four blue edges all meet vertex $5$, so they cannot contain a blue triangle: any three vertices chosen from $V$ include at most two of those four blue edges unless the triple contains only vertex $5$ and two others, in which case it has exactly two blue edges and one red edge.

Check: the restriction to $\{1,2,3\}$ retains $3\cdot2/2=3$ edges, namely $12,13,23$, and all three are in the red list. The blue edges total $4$, and no triple has three blue edges, as the full triple check confirms.

Worked Example: Restricting in the Second Target

Let $G=K_6$, with vertex set $V=\{1,2,3,4,5,6\}$. Colour all ten edges within $\{1,2,3,4,5\}$ red and the five edges $16,26,36,46,56$ blue. This specifies every edge: $|E(K_6)|=6\cdot5/2=15$, while the colour lists have $10+5=15$ edges.

The red vertices $\{1,2,3,4,5\}$ form a red $K_5$. Restricting to $\{1,2,3,4\}$ gives the six red edges $12,13,14,23,24,34$, a red $K_4$. Restricting instead to $\{1,2,3\}$ gives the three red edges $12,13,23$, a red $K_3$. Thus this one specified clique displays both successive restrictions in the first target.

The blue edges form a star with centre $6$. Any set of three vertices either omits $6$, in which case all its edges are red, or contains $6$ and two other vertices, in which case it has two blue edges to $6$ and one red edge between the other two vertices. Hence no triple is a blue triangle.

Check: the red $K_5$ has $5\cdot4/2=10$ edges; its $K_4$ restriction has $4\cdot3/2=6$ edges; and its $K_3$ restriction has $3\cdot2/2=3$ edges. The edge lists in each restriction contain exactly those numbers, and all are red.

What the Laws Do—and Do Not—Say

Symmetry and monotonicity are structural laws. Symmetry identifies two Ramsey numbers by showing that swapping the colours converts one defining property exactly into the other. Monotonicity is a one-way comparison: any clique of a given colour and size contains smaller cliques of that colour. Neither proof constructs an avoiding colouring, nor does either compute a numerical Ramsey number.

A common mistake is to reverse the restriction argument. From the fact that a red $K_{s+1}$ contains a red $K_s$, one may conclude that forcing a red $K_{s+1}$ or a blue $K_t$ also forces a red $K_s$ or a blue $K_t$. One may not conclude that a red $K_s$ extends to a red $K_{s+1}$. For example, in the $K_5$ colouring above, $\{1,2,3\}$ is a red $K_3$, but $\{1,2,3,5\}$ is not a red $K_4$, since its edges to $5$ are blue. The valid proof uses a larger clique to obtain a smaller one, not the reverse.

Likewise, the statement $R(s,t)\le R(s+1,t)$ does not assert $R(s,t)<R(s+1,t)$. The restriction proof establishes only the non-strict inequality. To prove strict growth or equality for particular targets requires additional arguments; neither follows merely from colour exchange or clique restriction.

Check Your Understanding

Use the definition of the forcing property and the two laws proved here.

Explain why interchanging red and blue is reversible and how that gives $R(s,t)=R(t,s)$.
In a red-blue colouring of $K_n$, why does a red $K_{s+1}$ contain a red $K_s$? State which vertices and edges are retained.
Give the direct restriction argument for $R(s,t)\le R(s,t+1)$.
Use repeated monotonicity to compare $R(s,t)$ and $R(s+2,t+3)$.
Why does the restriction argument not prove that the monotonicity inequalities are strict?

Symmetry and Monotonicity Laws for Ramsey Numbers

What You'll Learn