A from-scratch GPU attack on the Ramsey number R(5,5)

Overview

R(5,5) is one of the oldest open problems in combinatorics: the smallest party at which five people must be either all mutual friends or all mutual strangers. It is known only to lie between 43 and 46, and the lower bound of 43 has stood unmoved since 1989.

The target was a single object — a two-colouring of the complete graph on 43 vertices with no monochromatic clique of five. Finding one would push the bound to 44. Checking a candidate is effortless for a machine; finding one is the hard part. That asymmetry is the whole game.

I built a zero-dependency CUDA solver that runs fifty thousand independent searches in parallel on a single RTX 5090: an exhaustive circulant sweep, then GPU simulated annealing, then branch-and-bound on the surviving conflicts. One binary, compiled with nvcc, no external libraries.

Every path converged on the same wall — a floor of exactly two monochromatic cliques, always two five-cliques sharing a four-clique. Force it to break and an identical obstruction reappears elsewhere. Across half a million annealing runs the structure never changed.

The bound did not move. But the map of why it doesn't is the contribution: the first dedicated GPU attack on a diagonal Ramsey number, a proof that flag algebras cannot settle the question, and the first empirical measurement of matrix-product-state bond-dimension scaling for Ramsey factor graphs.