Verified Certificates via SAT and Computer Algebra Systems for the Ramsey 𝑹 ⁑ ( πŸ‘ , πŸ– ) \boldsymbol{R(3,8)} and 𝑹 ⁑ ( πŸ‘ , πŸ— ) \boldsymbol{R(3,9)} Problems

Zhengyu Li, Conor Duggan, Curtis Bright, Vijay Ganesh Β· 2025

Read Verified Certificates via SAT and Computer Algebra Systems for the Ramsey 𝑹 ⁑ ( πŸ‘ , πŸ– ) \boldsymbol{R(3,8)} and 𝑹 ⁑ ( πŸ‘ , πŸ— ) \boldsymbol{R(3,9)} Problems by Zhengyu Li, Conor Duggan, Curtis Bright, Vijay Ganesh (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2502-06055.txt.

Introduction

Ramsey numbers ask how large a network must be before a pattern becomes unavoidable, and two famous values rest on computer searches nobody could independently check. Zhengyu Li and co-authors produced verifiable certificates for the numbers R(3,8) and R(3,9). Their tool weds a SAT solver to a computer algebra system, so each step of the search carries a checkable proof.

The hybrid solved in hours or days what a top SAT solver alone could not finish in a week. A parallel cube-and-conquer scheme scaled it to the harder case. The certificates are the first for these values that others can verify end to end. The authors aim the method at other long-trusted computational results.

Catalog record

CREATORZhengyu Li, Conor Duggan, Curtis Bright, Vijay Ganesh
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE40 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2502-06055

Browse the full library Β· About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Verified Certificates via SAT and Computer Algebra Systems for the Ramsey 𝑹 ⁑ ( πŸ‘ , πŸ– ) \boldsymbol{R(3,8)} and 𝑹 ⁑ ( πŸ‘ , πŸ— ) \boldsymbol{R(3,9)} Problems Zhengyu Li, Conor Duggan, Curtis Bright, Vijay Ganesh Abstract The Ramsey problem R ⁑ ( 3 , k ) R(3,k) seeks to determine the smallest value of n n such that any red/blue edge coloring of the complete graph on n n vertices must either contain a blue triangle (3-clique) or a red clique of size k k . Despite its significance, many previous computational results for the Ramsey R ⁑ ( 3 , k ) R(3,k) problem such as R ⁑ ( 3 , 8 ) R(3,8) and R ⁑ ( 3 , 9 ) R(3,9) lack formal verification. To address this issue, we use the software MathCheck to generate certificates for Ramsey problems R ⁑ ( 3 , 8 ) R(3,8) and R ⁑ ( 3 , 9 ) R(3,9) (and symmetrically R ⁑ ( 8 , 3 ) R(8,3) and R ⁑ ( 9 , 3 ) R(9,3) ) by integrating a Boolean satisfiability (SAT) solver with a computer algebra system (CAS). Our SAT+CAS approach significantly outperforms traditional SAT-only methods, demonstrating a significant improvement in runtime. For instance, our SAT+CAS approach solves R ⁑ ( 8 , 3 ) R(8,3) sequentially in 18.5 hours, while a SAT-only approach using the state-of-the-art CaDiCaL solver times out after 7 days. Additionally, in order to be able to scale to harder Ramsey problem like R ⁑ ( 9 , 3 ) R(9,3) we further optimized our SAT+CAS tool using a parallelized cube-and-conquer approach. Our results provide the first independently verifiable certificates for these Ramsey numbers, ensuring both correctness and completeness of the exhaustive search process of our SAT+CAS tool. 1 Introduction Ramsey Theory, introduced by Frank P. Ramsey in On a problem of formal logic Ramsey 1930 , studies the existence of ordered substructures within sufficiently large structures. The classical Ramsey problem seeks the smallest integer n (known as the Ramsey number) such that any red/blue edge coloring of the complete graph on n vertices must contain either a blue triangle or a red k -clique. This problem is often framed as the β€œparty problem”: determining the minimum number of guests required to ensure that either p guests all know each other or q guests are mutual strangers. Despite its simple formulation, computing Ramsey numbers is notoriously difficult, with only nine non-trivial values known to date, despite extensive research Radziszowski 2011 . Most contemporary methods of finding non-trivial Ramsey numbers rely heavily on the use of computer programs such as nauty McKay and Piperno 2014 to enumerate Ramsey graphs exhaustively. However, nauty cannot generate a formal certificate certifying that the enumeration is indeed exhaustive, thus raising the possibility that these results may have errors in them. In this paper, we apply the software MathCheck Bright et al. 2016 that combines satisfiability solvers with computer algebra systems (SAT+CAS) Bright et al. 2022 to not only produce formal certificates for Ramsey numbers but also achieve significant speedups compared to SAT-only approaches. A key component of our implementation is the use of the IPASIR-UP interface Fazekas et al. 2023 , which facilitates seamless integration of external learned clause addition within modern SAT solvers. Specifically, we leverage IPASIR-UP to implement the CaDiCaL+CAS framework as part of MathCheck . In this work, we focus on providing certificates of completeness for the exhaustive search components required to determine R(3,k) and R(k,3) . It is important to emphasize that our approach does not constitute a formal proof of the Ramsey number. Instead, our certificates ensure correctness and completeness for the parts of the proof that involve exhaustive graph enumeration. 1.1 Our Contributions 1) Certified Ramsey Number: In this paper, we extend the well-known SAT+CAS tool MathCheck Zulkoski et al. 2015 (see Figure 1 ) to solve Ramsey problems of type R(3,k) and R(k,3) , and provide certificates of correctness. 1 1 1 All results can be reproduced at https://github.com/ConDug/MathCheckRamsey . These certificates ensure the correctness of the exhaustive search process of our tool. 2 2 2 We cannot claim complete formal proofs of these Ramsey numbers since their SAT encodings have not been formally verified. We verify the values of two Ramsey numbers for k=8 McKay and Min 1992 and k=9 Grinstead and Roberts 1982 , whose proofs rely heavily on graph enumeration. To our knowledge, these are the only two remaining known Ramsey numbers that have yet to be verified. 2) Speedup over SAT-only approaches: We show that our sequential and parallel SAT+CAS tools significantly outperform SAT-only approaches (see Table 2 ). This speedup is achieved through the isomorph-free exhaustive generation technique employed by MathCheck , which reduces the search space by dynamically blocking symmetric branches. 3) Parallel Cube-and-Conquer SAT+CAS MathCheck : We introduce a parallel cube-and-conquer SAT+CAS tool by integrating AlphaMapleSAT Jha et al. 2024 as the cubing solver and MathCheck as the conquering solver. We solved and certified R(8,3)=28 in 8 hours of wall clock time, and in doing so decreased the total CPU time spent solving to 6.2 hours (while the sequential version spent 18.5 hours just solving), and solved and verified R(9,3)=36 in 26 hours (while the sequential version timed out after 7 days). 2 Preliminaries 2.1 SAT+CAS for Combinatorial Problems A conflict-driven clause learning (CDCL) satisfiability (SAT) solver takes as input a Boolean formula in conjunctive normal form (CNF) and determines whether there exists an assignment of variables such that the formula evaluates to True, in which case the formula is satisfiable (SAT). Otherwise, the formula is unsatisfiable (UNSAT). Thanks to the rich advancement made by the SAT community, state-of-the-art CDCL SAT solvers can solve many instances with millions of variables efficiently Ganesh and Vardi 2021 . However, SAT solvers face challenges when solving hard combinatorial problems such as the Ramsey problem due to the large amount of symmetry in the search space. Computer Algebra Systems (CASs) such as Maple, Mathematica, Magma, and SageMath are storehouses of mathematical knowledge and contain state-of-the-art algorithms from a broad range of mathematical areas. Therefore, many mathematical properties can be easily expressed in a CAS, whereas an off-the-shelf SAT solver is limited to expressions in Boolean logic. Both SAT and CAS have their drawbacks when solving combinatorial problems. SAT solvers can perform scalable searches but lack the mathematical domain knowledge required to prune out symmetries in the search space. On the other hand, CASs have rich mathematical capabilities but lack scalability when dealing with enormous search spaces. To combine the best of both worlds, we leverage MathCheck to dynamically provide mathematical context to the SAT solver to only enumerate non-isomorphic graphs in the search space. More specifically, we use a CAS to generate blocking clauses that are passed to the SAT solver dynamically via a programmatic interface Ganesh et al. 2012 . These clauses block the SAT solver from exploring symmetric branches of the search tree. We elaborate on this technique in detail in Section 5 . The SAT+CAS paradigm has been applied to solving hard combinatorial problems such as the Williamson conjecture Bright et al. 2020 , Lam’s problem Bright et al. 2021 , Rota’s

Read the complete text