Conor Duggan — accepted AI-conference papers

2025

Verified Certificates via SAT and Computer Algebra Systems for the Ramsey R(3,8) and R(3,9) Problems

Zhengyu Li, Conor Duggan, Curtis Bright, Vijay Ganesh

IJCAI 2025

The Ramsey problem R(3,k) seeks to determine the smallest value of n such that any red/blue edge coloring of the complete graph on n vertices must either contain a blue triangle (3-clique) or a red clique of size k. Despite its significance, many previous computational results for the Ramsey R(3,k)

Cited by 0 Source ↗PDF ↗code ↗Scholar ↗

2024

A SAT + Computer Algebra System Verification of the Ramsey Problem R(3, 8) (Student Abstract)

Conor Duggan, Zhengyu Li, Curtis Bright, Vijay Ganesh

AAAI 2024technical

The Ramsey problem R(3,8) asks for the smallest n such that every red/blue coloring of the complete graph on n vertices must contain either a blue triangle or a red 8-clique. We provide the first certifiable proof that R(3,8) = 28, automatically generated by a combination of Boolean satisfiability (…

Cited by 2 Source ↗PDF ↗Scholar ↗