遇见数据集

Extension-rigidity of the known (5,5,42) Ramsey graphs, machine-certified

收藏
Zenodo2026-07-22 更新2026-08-01 收录
官方服务:

资源简介:

Self-contained verification artifact. For every one of the 656 known (5,5,42) Ramsey graphs (328 representatives up to complementation, from Brendan McKay's public catalogue), a 42-variable extension CNF is shown unsatisfiable: no known (5,5,42) graph extends to a (5,5,43) graph. Certification per instance: two independent SAT solvers (CaDiCaL, kissat), DRAT proofs verified by drat-trim, a faithfulness check (each CNF re-derived from the graph and compared clause-for-clause), an anti-vacuity check on every unsat core, positive controls (delete-a-vertex instances answer SAT, witness-checked), a machine-checked complement lemma extending 328 representatives to all 656 graphs, and a Lean 4 exemplar certificate. Consequently R(5,5) = 43 if and only if the known catalogue is complete (open McKay-Radziszowski conjecture). No unconditional claim beyond the published bounds 43 <= R(5,5) <= 46 is made. Includes data with provenance and hashes, standard-library Python code, all 328 CNFs and DRAT proofs, verification tables from two independent runs, figures, and a compiled paper.

提供机构:
Zenodo
创建时间:
2026-07-22
二维码
社区交流群
二维码
科研交流群
商业服务