A Time-Limited Nonabelian Cayley Search Did Not Improve the Lower Bound for R(4,18)

Abstract

No improvement to the published lower bound for R(4,18) was obtained. The search evaluated 8 programs from a nonabelian strategy family using 10 model calls and stopped because of the wall-clock limit. The best proven order remained 204, so the established result remained R(4,18) >= 205, as reported in DS1 revision 18. This negative result rules out success only for the evaluated portion of the strategy family under this run, not for nonabelian constructions in general.

Problem

The Ramsey number R(4,18) is the least order at which every graph contains a clique of order 4 or an independent set of order 18. DS1 revision 18, dated 2026-04-24, gives the published lower bound R(4,18) >= 205 in Table IIa. Equivalently, the best proven construction has order 204.

The computational objective was to improve this lower bound. No such improvement was obtained. The contribution of this report is therefore a documented negative search result rather than a new Ramsey bound.

Method

The attempt used model-guided program search in the methodological line of AlphaEvolve and FunSearch. There were 10 model calls, from which 8 search programs were evaluated. The strategy family was nonabelian.

The best program restricted its group choices to specifications marked abelian === false. It constructed an undirected Cayley connection set by pairing every group element with its inverse. A seeded mulberry32 generator selected a candidate group and a conjugating element. Inversion-pair representatives were then partitioned into blocks under conjugation. Candidate connection sets were unions of these blocks, preserving inverse closure and a selected conjugation symmetry.

For a materialized connection set, the program computed its degree and a local triangle count, then passed the group specification and connection set to cayleyViolations for the Ramsey constraints. The central structural idea was therefore:

nonabelian group
  -> inverse-pair representatives
  -> conjugation blocks
  -> unions of blocks
  -> inverse-closed Cayley graph
  -> violation evaluation

This summarizes the supplied best program without asserting behavior beyond the available source fragment.

Results

The search did not improve the R(4,18) entry. The best proven order remained 204, and the established bound remained

R(4,18) >= 205.

The run evaluated 8 programs after 10 model calls. It stopped for wall_clock after 1359s. Operationally, this rules out only the evaluated portion of the nonabelian strategy family under this run configuration. It does not prove that the full family contains no suitable construction.

Verification

The reported result was compared with DS1 revision 18, Table IIa, whose published bound is 205. The supplied run record reports improvement: NO and contains no new Ramsey graph or independently checkable certificate for a stronger bound. Consequently, no stronger claim is made.

The search code enforced inverse closure when materializing Cayley connection sets and used cayleyViolations to evaluate the target clique and independent-set constraints. The available data do not establish that every candidate in the broader nonabelian family was examined.

Limitations

This searched one strategy family on one cell. A vertex-transitive (circulant) construction is a restriction, not a general search. More precisely, the supplied program used nonabelian Cayley graphs, which are vertex-transitive but are not necessarily circulant in the strict cyclic-group sense.

Only 8 programs were evaluated, and termination was caused by the wall-clock limit. The result therefore does not rule out unevaluated programs or unevaluated constructions within the same family. It also does not constitute an exhaustive nonexistence result.

Reproducibility

The exported search interface was:

search({ n, s, t, groups, deadlineMs, seed })

The exact execution command and the seed are not present in the supplied run record. They therefore cannot be reported without fabrication, and an exact rerun cannot be specified from the available data.

Recorded expenditure was $0.4697 of model tokens and 1359s wall clock. The run used 10 model calls, evaluated 8 programs, and stopped for wall_clock.

References

[
  {
    "id": "10.37236/21",
    "title": "Small Ramsey Numbers",
    "authors": "Stanisław P. Radziszowski",
    "year": 2026
  },
  {
    "id": "10.48550/arXiv.2603.09172",
    "title": "AlphaEvolve on Ramsey numbers",
    "authors": "See the resolvable arXiv DOI record",
    "year": 2026
  },
  {
    "id": "10.1038/s41586-023-06924-6",
    "title": "Mathematical discoveries from program search with large language models",
    "authors": "Bernardino Romera-Paredes et al.",
    "year": 2024
  }
]