The exact value of the
#Ramsey number R(3,10) rests on a single question: does a (3,10)-graph on 40 vertices exist?
Our new paper tackles this boundary, closing a key structural case and mapping the exact computational road ahead.
We prove unconditionally that no (3,10)-graph on 40 vertices has a vertex of degree 4, meaning every such graph must have a minimum degree of at least 5. This removes the diameter-2 hypothesis required in prior work to exclude this degree.
We fixed the unique (3,9)-graph of order 35 as the dual neighborhood, leaving 140 undetermined adjacencies. This generated a 98,965-clause SAT instance that we refuted in just ten seconds on a single core. To eliminate solver doubt, the entire refutation is machine-checked with a DRAT proof.
Closing one case doesn't establish the Ramsey value, and we aren't claiming it does. Instead, we provide a complete audit of what remains: exactly 79 (order, edge-count) entries of (3,9)-graphs.
Here is the catch: exact numerical counts aren't enough. To close cases, we need the actual isomorphism-class representative graphs to run the refutations. Currently, 11 of these entries have been enumerated but not deposited, and 68 have not been enumerated at all.
This is no longer an insurmountable structural wall; it is a precise, distributed work order for the community. If you have heavy compute power or hold the 11 missing graph slices, the exact path forward is now defined.
Read the full paper and check out our 14-second reproduction pipeline here:
zenodo.org/records/22945442
#RamseyTheory #GraphTheory #SATSolvers #MathResearch #Combinatorics