No Improvement to the Published Lower Bound for R(4,19): A Wall-Clock-Limited Coset Search

Abstract

This computational attempt did not improve the published lower bound for \(R(4,19)\). A coset-based search used 20 model calls and evaluated 13 programs before stopping at the wall-clock limit. The best proven order remained \(n=212\), establishing \(R(4,19)\ge 213\), equal to the bound in DS1 revision 18. Thus, the tested coset candidates yielded no improvement; the run does not exclude the coset family as a whole.

Problem

The target cell was \(R(4,19)\). DS1 revision 18, dated 2026-04-24, reports the lower bound 213 in Table IIa [DS1]. The computational objective was to improve that published bound by finding and verifying a larger Ramsey graph.

For a graph of order \(n\), absence of a \(K_4\) in the graph and a \(K_{19}\) in its complement proves \(R(4,19)>n\). The best proven order in this attempt was \(n=212\), so the established bound was

\[ R(4,19)\ge 213. \]

This matches, but does not improve, the cited bound.

Method

The strategy family was coset search, implemented through vertex-transitive Cayley/circulant graph constructions. The program-search framework follows the AlphaEvolve approach [AE], with FunSearch as methodological ancestry [FS].

The best search program used the following key idea:

1. Enumerate the units modulo the candidate graph order.
2. Generate multiplicative subgroups from selected units.
3. Pair connection representatives under inversion.
4. Partition those representatives into subgroup coset orbits.
5. Form candidate connection sets as unions of complete orbits.
6. Prioritize orbit unions by connection-set size, with seed-dependent hashing used to order ties.
7. Evaluate each resulting Cayley graph with cayleyViolations, retaining the lowest violation score and accepting a construction only when the score is zero and the returned validity flag is true.

The relevant structure of the supplied program is:

const parts = new Map();
const add = h => {
  const key = h.join(",");
  if (!parts.has(key))
    parts.set(key, cosetPartition(n, reps, x => G.inv(x), h));
};

add([1]);
add(units);
for (const u of units) add(generatedSubgroup(n, [u]));

for (const orbits of candidates) {
  // Enumerate unions of coset orbits in a seeded order.
  const S = selectedOrbits.flat();
  const v = cayleyViolations(choice.spec, S, s, t, 100000, 500000);
  if (Number(v.total) < bestScore) {
    bestScore = Number(v.total);
    if (bestScore === 0 && v.valid)
      return { group: choice.spec, connection_set: S };
  }
}

The search was deadline-aware throughout and stopped for wall_clock rather than after an exhaustive traversal of the coset family.

Results

The run made 20 model calls and evaluated 13 programs. It stopped because the wall-clock limit was reached.

The best proven order was \(n=212\), establishing \(R(4,19)\ge 213\). The published bound was therefore reproduced but not improved. Operationally, the negative result rules out only the coset candidates actually evaluated during this run. It is not an exhaustive exclusion of every coset construction.

Verification

Candidate graphs were checked through the program's cayleyViolations routine for forbidden cliques in the graph and its complement. The program treated a candidate as successful only when the total violation score was zero and the validity flag was true.

The resulting proof status remained: best \(n\) proven, 212; bound established, \(R(4,19)\ge 213\). No stronger bound was certified. This report therefore makes no claim of a new Ramsey-number bound.

Limitations

This computation searched one strategy family—coset constructions—on one cell, \(R(4,19)\). A vertex-transitive (circulant) construction is a restriction, not a general search over graphs.

The wall-clock stop also means that the implemented coset search was not exhausted. Consequently, the result does not rule out the coset family in full; it records only that the evaluated programs and candidates produced no improvement within this run.

Exact rerunning is additionally limited by missing provenance: neither the execution command nor the seed was included in the supplied computational record.

Reproducibility

• Exact command: not recorded in the supplied computational record.
• Seed: not recorded in the supplied computational record.
• Model calls: 20.
• Programs evaluated: 13.
• Stop reason: wall_clock.
• Cost: $0.6103 of model tokens and 1525s wall clock.

Because the exact command and seed are unavailable, bit-for-bit reproduction from the reported information alone is not possible. The method can be reconstructed from the supplied search program, but its seed-dependent candidate order cannot be recovered.

References

[
  {
    "id": "10.37236/21",
    "title": "Small Ramsey Numbers",
    "authors": "Stanisław P. Radziszowski",
    "year": 2026
  },
  {
    "id": "10.48550/arXiv.2603.09172",
    "title": "AlphaEvolve: A Coding Agent for Scientific and Algorithmic Discovery",
    "authors": "Matej Balog et al.",
    "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
  }
]