Colorings as Lower-Bound Certificates
A Ramsey number asks when every edge-coloring must contain a monochromatic clique of a specified size. To prove that a Ramsey number is larger than some integer \(n\), it is enough to give one coloring on \(n\) vertices that avoids the required monochromatic cliques. Such a coloring is a certificate: its edges are explicitly assigned colors, and the absence of the target cliques can be checked from its construction.
We consider finite simple graphs and color every edge of a complete graph either red or blue. For positive integers \(s,t\), 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 red or blue \(K_j\) means a set of \(j\) vertices for which every pair has that color.
The direction of this inequality matters. A coloring on \(n\) vertices without the target cliques shows that the defining property of \(R(s,t)\) fails at \(n\); it does not show that the Ramsey number is at most \(n\). Earlier material on finite Ramsey numbers establishes that these numbers exist. Here the aim is to construct and verify particular lower-bound witnesses.
A General Certificate Principle
One way to specify a two-coloring is to choose a simple graph \(H\) on a vertex set \(V\), color its edges red, and color all remaining pairs blue. The blue edges are precisely the edges of the complement of \(H\). A clique in \(H\) is a set whose pairs are all red. An independent set in \(H\) is a set with no red pair, so all its pairs are blue.
Proof. Suppose a set of \(s\) vertices formed a red \(K_s\). Every pair within that set would be an edge of \(H\), so those vertices would form a clique of size \(s\) in \(H\), contrary to the hypothesis. Suppose instead that a set of \(t\) vertices formed a blue \(K_t\). No pair within that set would be an edge of \(H\), so the set would be independent in \(H\), again contrary to the hypothesis. Thus the coloring has neither required monochromatic clique. By the definition of \(R(s,t)\), failure of the defining property on \(n\) vertices implies \(R(s,t)>n\), which for an integer Ramsey number is \(R(s,t)\ge n+1\). \(\square\)
This principle separates a construction into two tasks: specify the red graph and then check its cliques and independent sets. A vertex partition can make those checks immediate; an arithmetic rule can give a larger, more structured example.
Worked Example: A Partition Coloring on Four Vertices
Partition \(V=\{1,2,3,4\}\) into \(A=\{1,2\}\) and \(B=\{3,4\}\). Let the red edge set be all pairs crossing between the parts, \(E_R=\{13,14,23,24\}\). Color the remaining pairs \(E_B=\{12,34\}\) blue. Together the two sets contain all six pairs of \(K_4\).
A red triangle would need three vertices with every pair crossing between \(A\) and \(B\). Among any three vertices, at least two lie in the same part, and their pair is blue, so there is no red triangle. A blue triangle is also impossible: the blue edges are just \(12\) and \(34\), which are disjoint and do not contain three vertices with all three pairs blue.
Check: there are \(4\cdot3/2=6\) pairs altogether, and \(|E_R|+|E_B|=4+2=6\). The partition rule therefore gives a coloring of every edge, and it has no monochromatic \(K_3\). This proves \(R(3,3)\ge5\), though a larger witness is possible.
The Five-Cycle Witness for \(R(3,3)\)
A cycle gives a particularly economical construction. Color the edges of a 5-cycle red and all other pairs blue. The complement of this cycle on five vertices is another 5-cycle, so neither color contains a triangle.
Worked Example: Coloring \(K_5\) with No Monochromatic Triangle
Take \(V=\{1,2,3,4,5\}\), with red edge set \(E_R=\{12,23,34,45,51\}\). The blue edge set consists of the other pairs: \(E_B=\{13,14,24,25,35\}\).
The red edges form the cycle \(1,2,3,4,5,1\). A cycle with five vertices has no triangle among its cycle edges: each vertex is incident with only its two cycle neighbors, and those two neighbors are not adjacent by a red edge. For blue, the listed edges form the cycle \(1,3,5,2,4,1\). The same direct check applies: each vertex has only its two cycle neighbors as blue neighbors, and those neighbors are not joined by a blue edge. Thus there is neither a red nor a blue triangle.
Check: \(K_5\) has \(5\cdot4/2=10\) edges, while the two color classes each have five edges, for a total of \(5+5=10\). The red and blue edge lists are disjoint and together account for every pair. This witness proves \(R(3,3)>5\), so \(R(3,3)\ge6\). The earlier exact value \(R(3,3)=6\) shows that this lower bound is sharp.
A Residue-Based Witness for \(R(4,4)\)
For a larger example, arithmetic modulo a prime can specify all edge colors at once. Use the vertex set \(V=\{0,1,\dots,16\}\), with arithmetic on vertex differences taken modulo \(17\). The nonzero squares modulo \(17\) are \(Q=\{1,2,4,8,9,13,15,16\}\). Color a pair \(uv\) red when \(v-u\) modulo \(17\) belongs to \(Q\), and blue otherwise. This rule does not depend on the order of \(u,v\): if \(q\in Q\), then \(-q\) modulo \(17\) is also in \(Q\). It therefore defines a coloring of the unordered pairs of a simple complete graph.
We first check the red neighbors of vertex \(0\), which are exactly \(Q\). The red edges among those eight vertices can be verified by subtracting their labels modulo \(17\). The resulting neighbor table lists, for each \(x\in Q\), its red neighbors that also belong to \(Q\):
| \(x\) | Red neighbors of \(x\) within \(Q\) |
|---|---|
| 1 | 2, 9, 16 |
| 2 | 1, 4, 15 |
| 4 | 2, 8, 13 |
| 8 | 4, 9, 16 |
| 9 | 1, 8, 13 |
| 13 | 4, 9, 15 |
| 15 | 2, 13, 16 |
| 16 | 1, 8, 15 |
For example, \(1\) is red-adjacent within \(Q\) to \(2,9,16\), since their differences from \(1\) are \(1,8,15\), all in \(Q\). The other entries are obtained by the same difference test. In every row, no pair among the three listed neighbors is a red edge: checking their differences against \(Q\) gives no member of \(Q\). Consequently, the red graph induced on \(Q\) has no triangle.
If there were a red \(K_4\), translate all its vertex labels by the negative of one of its vertices. Translation preserves differences modulo \(17\), hence preserves colors. The translated \(K_4\) would contain \(0\), and its other three vertices would be red neighbors of \(0\), hence members of \(Q\). Those three vertices would form a red triangle in the graph induced on \(Q\), which the table rules out.
It remains to rule out blue \(K_4\)s. The nonzero nonsquares are \(N=\{3,5,6,7,10,11,12,14\}\), exactly the blue neighbors of \(0\). Since \(3\notin Q\), multiplication by \(3\) maps \(Q\) onto \(N\) and swaps the two colors of differences: multiplying a square by a nonsquare gives a nonsquare, and multiplying a nonsquare by \(3\) gives a square modulo \(17\). Thus the blue graph induced on \(N\) is isomorphic to the red graph induced on \(Q\), so it too has no triangle. A blue \(K_4\), translated to include \(0\), would require a blue triangle among \(N\), a contradiction. This proves the claim.
Worked Example: Checking Edges in the Residue Coloring
Take the pair \(0,4\). Its difference is \(4\in Q\), so \(04\) is red. For the pair \(0,3\), the difference \(3\notin Q\), so \(03\) is blue. For the pair \(1,9\), the difference is \(9-1=8\in Q\), so \(19\) is red. Reversing its order gives \(1-9=-8\equiv9\pmod {17}\), also in \(Q\), confirming that the rule gives the same color to the unordered pair.
As a local check on the no-red-\(K_4\) argument, the red neighbors of \(0\) are \(Q\). The table gives the red neighbors of \(1\) within this set as \(2,9,16\). Their pairwise differences are \(9-2=7\), \(16-2=14\), and \(16-9=7\) modulo \(17\); none belongs to \(Q\). Hence these three neighbors do not make a red triangle with \(1\) inside the neighborhood of \(0\).
Check: The eight entries in \(Q\) are precisely the nonzero squares: \(1^2,\dots,8^2\) modulo \(17\) give \(1,4,9,16,8,2,15,13\). The eight elements of \(N\) are the remaining nonzero residues. The coloring therefore assigns one color to every pair with unequal endpoints. By the claim it has no monochromatic \(K_4\), giving \(R(4,4)>17\), or \(R(4,4)\ge18\).
Why Explicit Verification Matters
A construction is useful as a lower-bound proof only when it specifies every edge color and establishes that the forbidden monochromatic clique is absent. A picture may suggest the intended coloring, but a written rule and a check make the certificate reproducible. For a small example, listing both color classes is often clearest. For a larger example, a modular rule can specify every pair compactly, while a neighborhood argument reduces the clique check to a smaller calculation.
Common mistake: If a coloring on \(17\) vertices has no monochromatic \(K_4\), it is incorrect to conclude \(R(4,4)\le17\). The coloring shows that the defining property fails at \(17\), so the correct conclusion is \(R(4,4)>17\). An upper bound would require proving that every coloring on a specified number of vertices contains one of the target cliques.
It is also not enough to check that the red graph has no \(K_4\). A valid witness for the diagonal number must avoid a blue \(K_4\) as well. In the residue construction, the symmetry between squares and nonsquares supplies that second check; in other constructions it must be verified separately.
Check Your Understanding
For each question, distinguish the construction rule from the verification that it avoids the target cliques.
- Why does a coloring of \(K_n\) with no red \(K_s\) and no blue \(K_t\) imply \(R(s,t)\ge n+1\), rather than \(R(s,t)\le n\)?
- In the four-vertex partition example, list the red and blue edges and explain separately why neither color contains a triangle.
- Write the blue edge set in the five-cycle example as the cycle order \(1,3,5,2,4,1\). Why does that establish the absence of a blue triangle?
- For the modular coloring, why does translating every vertex label by the same residue preserve edge colors?
- Explain why checking only the red neighborhood of \(0\) would not, by itself, rule out blue \(K_4\)s. What additional symmetry check is used?