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