Improved lower bounds for complex network colorings in Ramsey theory
Lower bounds for Ramsey numbers: $\mathrm{R}(6,8)\ge 135$ and $\mathrm{R}(8,10)\ge 345$
Discrete Mathematics
Summary
Ramsey numbers are a way to understand how orderly or messy connections among points must become. The paper proves that two specific Ramsey numbers, R(6,8) and R(8,10), are bigger than previously known, meaning larger groups can avoid certain patterns of connections. The authors created explicit examples showing these larger sizes and used computer programs, some written by an AI assistant, to check them carefully. They improved known values by adding points and adjusting the connections using specialized search methods.
What this means in practice
- •For algorithm designers: Use improved bounds on Ramsey numbers to benchmark and refine combinatorial and graph search algorithms.
- •For software testing teams: Apply hard instances from these colorings to stress-test software dealing with large network structures and constraint satisfaction.
Authors
Fritz Cremer
Abstract
We prove the lower bounds $\mathrm{R}(6,8)\ge 135$ and $\mathrm{R}(8,10)\ge 345$, improving the bounds 134 and 343 listed in the April 2026 revision of Radziszowski's dynamic survey. We give explicit red/blue colorings of $K_{134}$ with no red $K_6$ or blue $K_8$, and of $K_{344}$ with no red $K_8$ or blue $K_{10}$, and verify them with two independently written exhaustive clique checkers. Starting from published colorings, we find these witnesses by adding vertices and repairing the resulting monochromatic cliques through local search. The search uses exact conflict counts, preparation moves aimed at making remaining cliques cheaper to break, and mutations followed by repair. A loss based on the largest monochromatic clique containing each edge yielded a useful intermediate state for the $\mathrm{R}(6,8)$ construction. Guided by the author, an AI coding agent wrote and ran the search code; we describe the methods and document the ancestry of the resulting colorings.