What a Ramsey Number Measures
Ramsey numbers answer a forcing question. If every edge of a complete graph is coloured red or blue, how many vertices guarantee a red clique of a specified size or a blue clique of another specified size? The number is not determined by one convenient colouring: it describes what happens for every colouring at that order.
All graphs in this tutorial are finite and simple. The complete graph \(K_n\) has \(n\) vertices, with an edge between every pair of distinct vertices. A clique of order \(s\), or \(K_s\), is a set of \(s\) vertices whose every pair is joined by an edge. In a red-blue edge-colouring, such a clique is monochromatic when all its edges have the same colour. We take \(s,t\ge 2\), so a monochromatic clique in question has at least one edge.
The quantifiers are essential. To show that a particular \(n\) has the required forcing property, one must consider every red-blue colouring of \(K_n\). To show that an order \(n\) does not have the property, it is enough to give one colouring of \(K_n\) with neither target. Thus, a single avoiding colouring provides evidence about a lower bound; it does not by itself prove that the next order always forces a target.
The standard finite Ramsey theorem states that \(R(s,t)\) exists and is finite for every \(s,t\ge2\). Its proof is developed through the neighborhood recurrence and induction in the later material on Ramsey numbers. Here we use the theorem only to know that the least order in the definition exists; the examples below do not require a general upper-bound calculation.
Red Graphs and Blue Complements
A colouring can be recorded as a graph. Let \(G_R\) have the same vertex set as \(K_n\), and put precisely the red edges into \(E(G_R)\). Every edge not in \(G_R\) is blue, so the blue graph is the complement \(\overline{G_R}\): it has an edge exactly where \(G_R\) does not.
Proof. A set of \(s\) vertices is a red \(K_s\) exactly when every pair in the set is a red edge. Red edges are precisely the edges of \(G_R\), so this is exactly the condition that the set is a clique of order \(s\) in \(G_R\). A set of \(t\) vertices is a blue \(K_t\) exactly when every pair is blue. Since every pair is either red or blue, this means that none of its pairs is an edge of \(G_R\), which is exactly an independent set of order \(t\) in \(G_R\). \(\square\)
This translation is useful because it lets us reason about one graph rather than repeatedly switching between two lists of coloured edges. It also explains why Ramsey questions naturally connect clique-finding with independent-set-finding. The colouring itself still assigns one of two colours to every edge: an edge cannot be omitted or given both colours.
Small Ramsey Numbers and Direct Checks
Worked Example: The First Nontrivial Forcing Case
Determine \(R(2,2)\) directly from the definition. For order \(n=1\), the complete graph \(K_1\) has no edges, so it contains neither a red \(K_2\) nor a blue \(K_2\). Thus order \(1\) does not force either target. For order \(n=2\), \(K_2\) has one edge. In a red-blue colouring that edge is either red, giving a red \(K_2\), or blue, giving a blue \(K_2\). Therefore order \(2\) does force one target.
Combining the two checks, the least forcing order is \(2\), so \(R(2,2)=2\). This argument checks both parts needed for an exact value: failure at every smaller positive order and success at the claimed order.
Check: \(K_1\) has no pair of distinct vertices, while \(K_2\) has exactly one pair and its edge receives exactly one of the two colours. The conclusion follows directly from the definition.
Worked Example: A Four-Vertex Colouring Without a Monochromatic Triangle
Let \(V=\{1,2,3,4\}\), and colour the edges of \(K_4\) red on \(E_R=\{12,23,34,14\}\) and blue on \(E_B=\{13,24\}\). These sets contain four and two edges, respectively, and together list all six pairs of vertices. Check each of the four possible three-vertex sets:
- \(\{1,2,3\}\): edges \(12,23\) are red and \(13\) is blue.
- \(\{1,2,4\}\): edges \(12,14\) are red and \(24\) is blue.
- \(\{1,3,4\}\): edges \(14,34\) are red and \(13\) is blue.
- \(\{2,3,4\}\): edges \(23,34\) are red and \(24\) is blue.
Every triple contains both colours, so this colouring has neither a red \(K_3\) nor a blue \(K_3\). In particular, order \(4\) does not force one of those targets; in the notation of the definition, \(R(3,3)>4\). This example establishes only failure at order \(4\), not the exact value of \(R(3,3)\).
Check: there are \(\binom{4}{2}=4\cdot3/2=6\) edges, and \(E_R\) and \(E_B\) have \(4+2=6\) distinct edges. The four listed triples are all the three-vertex subsets, so none has been skipped.
Worked Example: Finding One of the Target Cliques
Let \(V=\{1,2,3,4,5\}\), with red edges \(E_R=\{12,13,14,15\}\) and blue edges \(E_B=\{23,24,25,34,35,45\}\). The red edges are exactly those incident with vertex \(1\); the six edges among vertices \(2,3,4,5\) are blue.
The set \(\{2,3,4,5\}\) has the six pairs \(23,24,25,34,35,45\), and all six appear in \(E_B\). Hence it is a blue \(K_4\). The red graph has no triangle: every red edge is incident with \(1\), while no pair among \(2,3,4,5\) is red. Any three-vertex set not containing \(1\) has no red edges, and any three-vertex set containing \(1\) has at most two red edges, both incident with \(1\).
Thus this colouring contains a blue \(K_4\), and it contains no red \(K_3\). It illustrates one outcome relevant to the target pair \((3,4)\), but one successful colouring cannot prove that every colouring of \(K_5\) has a target.
Check: the red and blue lists have \(4\) and \(6\) edges, giving \(4+6=10\) distinct edges, the number of pairs in a five-vertex complete graph, \(5\cdot4/2=10\). The six blue pairs on \(\{2,3,4,5\}\) verify the claimed \(K_4\).
What Counts as Evidence
There are two complementary ways to reason about a proposed Ramsey number. A colouring with no red \(K_s\) and no blue \(K_t\) on \(n\) vertices proves that \(n\) does not have the forcing property. Since the property is defined as holding at a particular order, the direct conclusion is limited to that order; proving a lower bound for the least forcing order requires an argument covering all smaller orders as well. By contrast, an upper-bound proof must show that an arbitrary colouring at the claimed order has at least one target.
For an exact value \(R(s,t)=n\), both sides are necessary:
- show that order \(n\) forces a red \(K_s\) or a blue \(K_t\);
- show that every smaller order fails to force them, typically by giving an avoiding colouring at order \(n-1\) and explaining why it also gives failure at smaller orders.
These tasks have different logical forms. A forcing statement begins with an arbitrary colouring and must cover all possibilities. An avoiding statement needs one carefully checked colouring. Keeping the quantifiers visible prevents an example from being mistaken for a complete proof.
Common Pitfall: Edge Counts Do Not Decide Clique Colourings
A common error is to argue that a colour occurring on many edges must contain a monochromatic triangle. The four-vertex example above gives a concrete correction. It has four red edges and two blue edges, yet it has no red or blue triangle. The red edges form the cycle \(1,2,3,4,1\); each possible triple includes one of the blue edges \(13\) or \(24\).
The mistake is to infer a local pattern of three mutually joined vertices from a total edge count alone. A monochromatic \(K_3\) requires all three edges of one particular triple to have the same colour. Counting how many edges have each colour does not identify such a triple. For larger targets the same caution applies: check the edges inside a candidate vertex set, not merely the overall number of red or blue edges.
Ramsey numbers organize the distinction between a local obstruction and a global guarantee. A specific colouring shows what can happen; a Ramsey number states when every colouring must contain one of the prescribed monochromatic structures. The finite Ramsey theorem guarantees that such a forcing order exists, while exact values require separate lower- and upper-bound arguments.
Check Your Understanding
For each question, state whether you need to inspect one colouring or prove a claim for every colouring.
- In the second worked example, which four vertex sets must be checked to rule out a monochromatic triangle?
- Explain why a red \(K_s\) in a colouring is a clique in the red graph, while a blue \(K_t\) is an independent set in that graph.
- What does one colouring of \(K_n\) with neither target establish about the forcing property at order \(n\)?
- For an exact claim \(R(s,t)=n\), identify the two distinct statements that must be proved.
- Why does knowing that one colour has more edges than the other not by itself establish a monochromatic triangle?