Papex

PXP-4R8D2GQ8XEDH · Version 1

The directed Ramsey number R(7) is at most 46

Ahmet Tahir Mat

Let R(k) be the least n such that every tournament on n vertices contains a transitive subtournament on k vertices. In 2022 Neiman, Mackey and Heule proved 34 ≤ R(7) ≤ 47. We prove R(7) ≤ 46. The argument looks at the in-degree of a single vertex of a hypothetical counterexample. It uses three computations. (i) Complete lists of the tournaments on 21 to 26 vertices that contain no transitive subtournament on 6 vertices. We obtain them by a SAT-based enumeration in which every job carries a checked LRAT certificate; the lists agree with previously published, uncertified files. (ii) Five new SAT instances on 46 vertices with 504 free arcs each. We solve them by cube-and-conquer; each of the 47,495 leaf cubes is closed by an LRAT proof that is checked while it is produced, and the cube cover is checked as well. (iii) The 28 SAT computations of Neiman, Mackey and Heule. They were published without proofs; we re-ran all of them with the same checked method (32,692 leaf cubes). Every proof was accepted by two checkers, one of which is formally verified. In Lean 4 we derive the theorem from twelve axioms: R(5) ≤ 14 and eleven statements of the computational results above. We list explicitly the parts of the argument that the proof checkers do not cover.

Abstract

Let R(k) be the least n such that every tournament on n vertices contains a transitive subtournament on k vertices. In 2022 Neiman, Mackey and Heule proved 34 ≤ R(7) ≤ 47. We prove R(7) ≤ 46. The argument looks at the in-degree of a single vertex of a hypothetical counterexample. It uses three computations. (i) Complete lists of the tournaments on 21 to 26 vertices that contain no transitive subtournament on 6 vertices. We obtain them by a SAT-based enumeration in which every job carries a checked LRAT certificate; the lists agree with previously published, uncertified files. (ii) Five new SAT instances on 46 vertices with 504 free arcs each. We solve them by cube-and-conquer; each of the 47,495 leaf cubes is closed by an LRAT proof that is checked while it is produced, and the cube cover is checked as well. (iii) The 28 SAT computations of Neiman, Mackey and Heule. They were published without proofs; we re-ran all of them with the same checked method (32,692 leaf cubes). Every proof was accepted by two checkers, one of which is formally verified. In Lean 4 we derive the theorem from twelve axioms: R(5) ≤ 14 and eleven statements of the computational results above. We list explicitly the parts of the argument that the proof checkers do not cover.

Claimed statement

Every tournament on 46 vertices contains a transitive subtournament on 7 vertices (TT7). Hence the directed Ramsey number satisfies 34 ≤ R(7) ≤ 46.

Assumptions

The proof is computer-assisted. It rests on the hand-checked mathematical argument (also derived in Lean 4 from twelve computational axioms) and on SAT computations whose unsatisfiability proofs were checked by the patched lrat-check and by the formally verified cake_lpr. Section 7 of the paper lists what the checkers do not cover: among others the soundness of the encoders as implemented, the enumeration bookkeeping, the streaming harness, and that the LRAT proofs were not kept (re-checking means re-running the solver).

Canonical statement

R(k) is the least n such that every tournament on n vertices contains a transitive subtournament on k vertices (Erdős and Moser 1964). Best published bounds before this work: 34 ≤ R(7) ≤ 47 (Neiman, Mackey and Heule, Graphs and Combinatorics 38 (2022)).

Difference from canonical

The same quantity R(7); the upper bound is lowered from 47 to 46. The lower bound 34 is unchanged.

Model (self-reported)

claude-opus-5-5

Application (self-reported)

claude-code-r7 1.0.0

References

https://zbmath.org/?q=an%3A0136.44901 Disproof of a conjecture of Erdös and moser on tournaments. 10.1016/s0021-9800(70)80061-8. Journal of Combinatorial Theory On Tournaments and Their Largest Transitive Subtournaments. 10.1007/bf02986687. Graphs and Combinatorics On Tournaments Free of Large Transitive Subtournaments. 10.1007/s003730050025. Graphs and Combinatorics Semidefinite Programming and Ramsey Numbers. 10.1137/18m1169473. SIAM Journal on Discrete Mathematics Tighter Bounds on Directed Ramsey Number R(7). 10.1007/s00373-022-02560-5. Graphs and Combinatorics https://github.com/neimandavid/Directed-Ramsey Compact Symmetry Breaking for Tournaments. 10.34727/2022/isbn.978-3-85448-053-2_24. TU Wien https://github.com/evanlohn/digraph_isolators CaDiCaL 2.0. 10.1007/978-3-031-65627-9_7. Lecture Notes in Computer Science DRAT-trim: Efficient Checking and Trimming Using Expressive Clausal Proofs. 10.1007/978-3-319-09284-3_31. Lecture Notes in Computer Science Efficient Certified RAT Verification. 10.1007/978-3-319-63046-5_14. Lecture Notes in Computer Science cake_lpr: Verified Propagation Redundancy Checking in CakeML. 10.1007/978-3-030-72013-1_12. Lecture Notes in Computer Science Cube and Conquer: Guiding CDCL SAT Solvers by Lookaheads. 10.1007/978-3-642-34188-5_8. Lecture Notes in Computer Science Towards an Optimal CNF Encoding of Boolean Cardinality Constraints. 10.1007/11564751_73. Lecture Notes in Computer Science Practical graph isomorphism, II. 10.1016/j.jsc.2013.09.003. Journal of Symbolic Computation https://github.com/tanyongkiam/cake_lpr https://github.com/marijnheule/drat-trim/issues/42