Establishing lower bounds for Ramsey numbers is a classical family of hard combinatorial feasibility problems: one seeks a 2-coloring of the edges of $K_n$ avoiding a red $K_r$ and a blue $K_s$. Such witnesses have accumulated over decades through problem-specific discrete heuristics, with several key values remaining out of reach for generic methods. We replace direct search in graph space by continuous optimization on a hypercube relaxation, retaining binary structure through the oracle, the rounding, and a final exact verification.

Counting forbidden monochromatic cliques by a pseudo-Boolean polynomial $M(x)$ turns satisfiability into the minimization of a smooth multilinear objective over the unit hypercube $[0,1]^m$; since $M$ is affine in each coordinate, its continuous and integral minima coincide. The vanilla Frank-Wolfe method performs surprisingly well on this relaxation, even though the objective is non-monotone supermodular and only stationarity guarantees apply: its linear minimization oracle over the hypercube is available in closed form and returns a binary vertex at every step, anchoring the fractional iterates to concrete candidate colorings, and a conditional-expectations rounding then converts any iterate to a binary one without increasing the violation count.

This projection-free pipeline recovers a significant portion of the known lower-bound table and, most notably, reliably finds $42$-vertex graphs certifying $R(5,5) \geq 43$ — a long-standing benchmark that recent LLM-driven evolutionary search (AlphaEvolve, Nagda et al., 2026) does not report. We discuss the resulting multimodal solution landscape and the central open question: why Frank-Wolfe succeeds so well on a non-monotone supermodular objective for which no approximation guarantee is known.