57 vertices, and not one more

The question

A ring, some chords, and two things to avoid

Put m dots on a circle. Pick a few distances, say 1, 5 and 8, and join every pair of dots that sit exactly that far apart around the ring. That is a circulant graph, written Cay(Z_m, ±S). It looks the same from every dot, which is what makes it searchable.

Ramsey's theorem says a big enough graph must contain a triangle or a large set of dots with no edges between them (an independent set). A000789(n) asks for the largest circulant with no triangle and no independent set of size n. For n = 12 the answer has been known to be 48. For n = 13 OEIS is blank.

Half one · existence

Nine witnesses, checked as this page loaded

For every m from 49 to 57 there is a chord set that works: no triangle, and the largest independent set has 12 dots. Your browser just checked each one with an exact search (no sampling).

The m = 57 graph also has a second witness in a different orbit, ±{1, 4, 6, 9, 20, 23}. An earlier write-up called that one the canonical form of the first. It is not; both are valid, and they are not related by a unit multiplication. File: witness_m49_57.json, sha256 2b72fd199d85eab2a1cad50c59452b17d11ca165ec4579c635b25db63bdf041a.

Half two · impossibility

Every circulant on 58 to 68 dots fails

Three facts shrink the search from 2²⁹ chord sets at m = 58 to something a laptop eats in seconds:

• Degree is at most 12. In a triangle-free graph a dot's neighbours can't be joined to each other, so they form an independent set. This is a textbook fact, not a new lemma.
• Only dot 0 needs checking for triangles, because every dot looks the same.
• Multiplying every chord by a number coprime to m gives the same graph, relabelled, so one representative per orbit is enough.

For each orbit the search must produce 13 dots that are pairwise unjoined. Each such certificate is then re-checked with nothing but the distance rule, separately from the search code. Above 68, the classical bound R(3,13) ≤ 68 (Goedgebeur and Radziszowski, arXiv 1210.5826) finishes the job, so even m = 68 is covered twice.

Calibration

Does the method get the known answers right?

A checker that can only say yes is worthless, so the same code is run on every known term, n = 3 to 12. If it disagreed with OEIS anywhere, the n = 13 result would mean nothing.

Your turn

Try a chord set

The record

Checked, then corrected

The Foundry's first report called this "three open sequences solved" with a new lemma. An independent re-implementation (no shared code, same model family, so not fully independent) audited it on 24 October 2026. The numbers held. The story did not:

• It is one computation read three ways, not three results. The data files behind the three sequence IDs are byte-identical.
• The degree bound is classical.
• The draft cited R(3,13) ≤ 69. The current bound is 68.
• The m = 57 "canonical orbit" claim was wrong (see above).
• Writing this page turned up one more: the draft's totals line (1,317,031 sets, 74,366 orbits) does not add up. The per-m counts are right; their sum is 1,206,892 sets and 77,611 orbits, which is what the run above reports.

The method is explicit certificates checked by a second code path. No formal checker such as Lean has passed it, so this page says "checked", never "verified". For results held to that standard, see Erdős Check.