Exhaustive Search for Small Ramsey Colorings

Why Search for a Ramsey Lower-Bound Certificate?

For positive integers \(r,s\ge 2\), the Ramsey number \(R(r,s)\) is the least integer \(N\) such that every red-blue colouring of the edges of \(K_N\) contains either a red \(K_r\) or a blue \(K_s\). To prove \(R(r,s)>n\), it is enough to give one red-blue colouring of \(K_n\) containing neither forbidden clique. Such a colouring is a lower-bound certificate: checking it establishes that \(n\) vertices do not suffice.

For small \(n\), a computer can search all colourings, but an unstructured list of colourings is difficult to inspect. Backtracking organizes the search as a tree of partial assignments. At each step it chooses a still-uncoloured edge and branches by assigning it red or blue. If the assignments already made complete a forbidden monochromatic clique, that branch is discarded: no future choice can remove the clique. This tutorial develops the method and explains both what it can certify and why it is exhaustive.

When we describe a red-blue colouring, we give the vertex set and the two edge sets explicitly. Every edge of \(K_n\) belongs to exactly one of these sets. If the red and blue edge sets are \(E_R\) and \(E_B\), then \(E_R\cap E_B=\varnothing\) and \(E_R\cup E_B=E(K_n)\).

The Backtracking Search

Fix an order \(e_1,\ldots,e_m\) of the edges of \(K_n\), where \(m=\binom n2\). A search state consists of a partial colouring of an initial segment of this edge list. At each state, the search tests whether a forbidden clique has been completed. If so, it returns from that branch. If not, it assigns the next edge red and searches that branch, then assigns it blue and searches that branch. When all \(m\) edges have been assigned, the colouring is a valid certificate.

The test in Step 2 must examine only completed cliques: all the edges of the candidate vertex set must already be assigned the required colour. The state may still have unassigned edges elsewhere. A completed forbidden clique stays completed in every extension of the state, which is the reason pruning is safe.

Proof. Suppose the partial colouring contains a fully assigned red \(K_r\). An extension assigns colours only to previously unassigned edges; it does not change the colours already assigned to edges of this \(K_r\). Thus this same vertex set remains a red \(K_r\) in every extension, so no extension is admissible. If instead the partial colouring contains a fully assigned blue \(K_s\), its edges also retain their assigned colours in every extension, so every extension contains that blue \(K_s\). Either way, no extension is admissible. \(\square\)

Proof. If the search returns a complete admissible colouring, it assigns every edge exactly one of the two colours and has passed the completed-clique test. By the definition of admissibility, it contains neither forbidden monochromatic clique. This proves one direction.

For the other direction, suppose some admissible complete colouring exists. Consider the search branch whose successive choices agree with that colouring. No partial state on this branch can contain a completed forbidden clique: such a clique would also appear in the assumed admissible complete colouring, since the assigned edges keep their colours. Thus the branch is never discarded by the test. It reaches a complete colouring, and that colouring is admissible, so the search can return it. Consequently, if every branch is discarded, there is no admissible colouring of \(K_n\). By the definition of \(R(r,s)\), every colouring of \(K_n\) then contains a red \(K_r\) or a blue \(K_s\), which implies \(R(r,s)\le n\). \(\square\)

This argument also explains the search’s scope. It proves a lower bound by exhibiting a colouring; it proves that a particular \(n\) has no certificate only after all branches have been explored. A run that stops at its first certificate answers the existence question positively, but does not enumerate or count all certificates.

Worked Searches and Certificates

What a Certificate Does—and Does Not—Show

A certificate is independently checkable: list the vertices and the red and blue edges, then test every \(r\)-vertex set for an all-red edge set and every \(s\)-vertex set for an all-blue edge set. If all tests pass, the certificate proves \(R(r,s)>n\). The number of tests is finite, so this verification does not depend on trusting the search procedure that found the colouring.

For a small instance, search can also settle the opposite question. If it explores every branch and discards them all, the correctness theorem proves that no certificate exists on \(n\) vertices. Combined with a certificate on \(n-1\) vertices, this can identify an exact Ramsey value. The search itself does not make an incomplete run into a proof: stopping early without finding a colouring, or without exhausting the branches, gives no conclusion that all colourings fail.

In practice, an implementation can improve speed by choosing an edge order that tends to complete likely forbidden cliques early. It can also keep track of which vertex sets have become fully assigned. These choices may change how soon a branch is discarded, but not the correctness argument, provided the program still considers both colours for each unassigned edge unless it has a valid pruning reason.

Common Mistake: Pruning Before a Clique Is Complete

A frequent error is to discard a partial state merely because it has \(r-1\) red edges among the vertices of a possible \(K_r\), even though one or more of the clique’s edges remain unassigned. For example, on \(V=\{1,2,3\}\), suppose \(12\) and \(13\) are red while \(23\) is unassigned. It is incorrect to prune this state as a red triangle: if the remaining edge \(23\) is assigned blue, the triangle is not monochromatic red. The correct test waits until all three edges have been assigned and are red. Pruning is justified by a completed obstruction, not by a partial resemblance to one.

The distinction is central to exhaustive search. The method is efficient because it avoids exploring extensions of a completed forbidden clique, but it remains reliable only when every discarded branch is known to have no admissible extension. Safe pruning and a complete branching rule turn a finite computation into a proof.