What a Coloring Certificate Shows
A finite Ramsey number asks when a monochromatic clique is unavoidable. A useful way to prove a lower bound is to give a specific coloring in which the target cliques do not occur. The coloring itself is a certificate: its edge lists make the claim checkable, while the absence of the target cliques proves that the bound holds.
All graphs in this tutorial are finite and simple. For integers \(s,t\ge2\), the Ramsey number \(R(s,t)\) is the least integer \(N\) such that every red-blue coloring of the edges of \(K_N\) contains either a red \(K_s\) or a blue \(K_t\). A clique is a set of vertices every two of which are adjacent in the graph being considered. A red \(K_s\) means that all pairs among its \(s\) vertices are red; a blue \(K_t\) is defined in the same way.
The word “all” matters: a coloring of only some edges is not a certificate. If \(V=\{1,\dots,n\}\), the full edge set consists of all unordered pairs of distinct vertices, and has \(\binom n2\) edges. A correct certificate must assign each of these pairs exactly one color.
Why a Certificate Proves a Lower Bound
Proof. Suppose first that a coloring of \(K_n\) contains neither target clique. If \(R(s,t)\le n\), restrict the coloring to any \(R(s,t)\) vertices. Every pair among those vertices retains its color, so the restricted coloring still has neither target clique. This contradicts the defining property of \(R(s,t)\), which says that every coloring on \(R(s,t)\) vertices has one of them. Therefore \(R(s,t)>n\).
For the converse, suppose \(n<R(s,t)\). If every coloring of \(K_n\) contained a red \(K_s\) or a blue \(K_t\), then \(n\) would have the defining property required of a Ramsey number. The least such integer would satisfy \(R(s,t)\le n\), contrary to \(n<R(s,t)\). Thus some coloring of \(K_n\) avoids both target cliques. \(\square\)
This characterization makes the task concrete. To establish a lower bound, one does not need to prove that every possible coloring fails; one gives a single coloring and verifies it. The verification has two separate parts: confirm the edge partition, then rule out the target clique in each color.
Worked Certificates
Worked Example: A Certificate for \(R(3,3)>5\)
Take \(V=\{1,2,3,4,5\}\). Color the edges red and blue as follows:
\(E_R=\{12,23,34,45,15\}\), and \(E_B=\{13,14,24,25,35\}\).
The complete graph \(K_5\) has \(\binom52=5\cdot4/2=10\) edges. These lists contain five edges each, are disjoint, and together list all ten pairs: \(12,13,14,15,23,24,25,34,35,45\). So this is a coloring of every edge, with no pair omitted or assigned two colors.
The red edges form the cycle \(1,2,3,4,5,1\). There is no red triangle: in a cycle of length five, each vertex has only its two consecutive neighbors, and those two neighbors are not adjacent. The blue edges form the cycle \(1,3,5,2,4,1\). The same check shows that there is no blue triangle. Thus neither color contains a \(K_3\), and the theorem gives \(R(3,3)>5\).
Check: The two listed cycles use all five vertices, and their edge sets are disjoint. The total is \(5+5=10=\binom52\), as required for a complete coloring.
Worked Example: A Certificate for \(R(3,4)>6\)
Let \(V=\{1,2,3,4,5,6\}\). Use the red edges \(E_R=\{12,23,34,45,56,16,14\}\), and color every other pair blue. Explicitly, \(E_B=\{13,15,24,25,26,35,36,46\}\).
The complete graph has \(\binom62=6\cdot5/2=15\) edges. The red and blue lists have seven and eight edges, respectively; they are disjoint and contain all fifteen pairs: \(12,13,14,15,16,23,24,25,26,34,35,36,45,46,56\).
The six edges \(12,23,34,45,56,16\) form a cycle of length six. The only extra red edge is \(14\). The cycle alone has no triangle. A triangle using the extra edge would need a common neighbor of 1 and 4 among the cycle edges. Their cycle-neighbor sets are \(\{2,6\}\) and \(\{3,5\}\), which have no common vertex. Hence there is no red triangle.
A blue \(K_4\) would be four vertices with no red edge between any pair. But the red edges include the three disjoint pairs \(12,34,56\). A set containing no red edge can contain at most one endpoint from each of these three pairs, so it has at most three vertices. There is therefore no blue \(K_4\). The coloring certifies \(R(3,4)>6\).
Check: Any four vertices include both endpoints of at least one of \(12,34,56\): choosing at most one from each pair gives at most \(1+1+1=3\) vertices. That red edge prevents those four vertices from forming a blue clique.
Worked Example: A Certificate for \(R(3,5)>7\)
Set \(V=\{1,2,3,4,5,6,7\}\). Let the red edges be the 7-cycle \(E_R=\{12,23,34,45,56,67,17\}\). The blue edge set is the complement within the pairs of \(V\): \(E_B=\{13,14,15,16,24,25,26,27,35,36,37,46,47,57\}\).
There are \(\binom72=7\cdot6/2=21\) pairs. The two lists have seven and fourteen edges, are disjoint, and together contain all 21 pairs. The red graph is a cycle of length seven, so it has no triangle: a triangle would require an edge between two neighbors of some cycle vertex, and the cycle has no such edge.
A blue clique is exactly a set of vertices with no red edge between any pair; such a set is called independent in the red graph. To bound its size, take any independent set \(S\) in the red 7-cycle. For each vertex in \(S\), take the next vertex around the cycle. These next vertices are all distinct, and none belongs to \(S\), because each is red-adjacent to its predecessor in \(S\). Thus \(S\) and its set of successors are disjoint subsets of the seven vertices, with the same size. Hence \(2|S|\le7\), so \(|S|\le3\). In particular, there is no red-independent set of size five, and therefore no blue \(K_5\). This coloring certifies \(R(3,5)>7\).
Check: The successor argument gives \(2|S|\le7\), hence \(|S|\le3\) because \(|S|\) is an integer. A blue \(K_5\) would require \(|S|=5\), which contradicts that bound.
A Reliable Verification Routine
For a proposed coloring, separate the bookkeeping from the clique argument. This prevents a correct-looking structural idea from concealing an omitted edge or a missed clique.
State \(V=\{1,\dots,n\}\), or another explicit set, and identify the complete graph being colored.
Give \(E_R\) and \(E_B\) explicitly. Check that their intersection is empty and that their union consists of every pair of distinct vertices.
Show that no \(s\)-vertex set has all its pairs in \(E_R\). A structural argument, such as a degree or neighborhood check, can shorten the verification, but it must cover every possible target clique.
Show that no \(t\)-vertex set has all its pairs in \(E_B\). Equivalently, such a set would have to contain no red edges, so an upper bound on red-independent sets may suffice.
Once both absences and the complete edge partition are verified, invoke the certificate theorem to conclude \(R(s,t)>n\).
The independent-set conversion is especially useful: a set is a blue clique precisely when each pair of its vertices is blue, which is precisely when none of its pairs is red. It does not require the red graph to be regular or connected. It is simply the complement relation between the two colors in a complete graph.
Common Pitfall: Ignoring an Extra Edge
A certificate can fail because an added edge creates a target clique, even when the underlying cycle itself is triangle-free. For example, on \(V=\{1,2,3,4,5\}\), let the red edges be \(12,23,34,45,51,13\), and let the blue edges be all remaining pairs. It is wrong to say “the red edges are a 5-cycle, so there is no red triangle”: the list contains the extra chord \(13\), and \(12,23,13\) are all red. They form a red triangle, so this coloring is not a certificate for \(R(3,t)\) for any \(t\).
The correction is to inspect the full edge list, including chords, before drawing conclusions from the named cycle. A valid lower-bound certificate needs both a complete coloring and a proof that every set of the target size fails to be a clique in its specified color. Listing only a cycle and saying “the rest is blue” can work, but only when “the rest” means every remaining pair and the blue clique check is also carried out.
How to Read the Result
A certificate proves a lower bound, not an exact Ramsey number. For instance, the first example establishes \(R(3,3)>5\), but by itself says nothing about whether the value is 6, 7, or larger. To prove equality, one also needs an upper-bound argument that every coloring at some specified order contains a target clique. The certificate has a deliberately narrower job: it gives a fully checkable obstruction at one order.
Likewise, the two colors need not play symmetric roles in a particular certificate. The red condition may be checked through triangles while the blue condition is checked through independent sets, as in the second example. What matters is that the stated target is absent in each required color and that every edge of the complete graph has been assigned exactly once.
Check Your Understanding
For each question, distinguish the edge-partition check from the clique-absence check.
- For \(V=\{1,2,3,4\}\), list all six pairs. What must be verified about two proposed color classes before they can define a coloring certificate?
- Why does a red-independent set of size \(t\) give a blue \(K_t\) when every pair is colored either red or blue?
- In the second worked example, explain why the red edges \(12,34,56\) rule out a blue \(K_4\), even though they do not list every red edge.
- For the red 7-cycle in the third example, reproduce the successor argument showing that an independent set has at most three vertices.
- Suppose an explicit coloring of \(K_n\) has no red \(K_s\) and no blue \(K_t\). State the strict lower bound on \(R(s,t)\) and explain why it is strict.