Computing the Ramsey number R(4,3,3) using abstraction and symmetry breaking

DOI10.1007/S10601-016-9240-3MaRDI QIDQ2398438zbMATH OpenOpenAlexFDO

Authors Michael Codish, M. Frank, Avraham Itzhakov, Alice Miller

Publication date 16 August 2017

Published in Constraints (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1510.08266

zbMATH Keywords

Ramsey numbersSAT solvingsymmetry breaking

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15)

Abstract: The number $R(4,3,3)$ is often presented as the unknown Ramsey number with the best chances of being found "soon". Yet, its precise value has remained unknown for almost 50 years. This paper presents a methodology based on emph{abstraction} and emph{symmetry breaking} that applies to solve hard graph edge-coloring problems. The utility of this methodology is demonstrated by using it to compute the value $R(4,3,3)=30$. Along the way it is required to first compute the previously unknown set $calR(3,3,3;13)$ consisting of 78{,}892 Ramsey colorings.

Recommendations

• The Ramsey number \(R(3,K_{10}-e)\) and computational bounds for \(R(3,G)\)
• On the Ramsey number R(4,6)
• scientific article; zbMATH DE number 1743974
• scientific article; zbMATH DE number 1308948
• scientific article; zbMATH DE number 2192105

Cites work

• R(4, 5) = 25
• A new method to construct lower bounds for van der Waerden numbers
• Boolean equi-propagation for concise and efficient SAT encodings of combinatorial problems
• Computing the van der Waerden number W(3,4)=293
• Constraints for symmetry breaking in graph representation
• Diamond-free degree sequence
• DRAT-trim: Efficient Checking and Trimming Using Expressive Clausal Proofs
• Every planar map is four colorable
• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• scientific article; zbMATH DE number 1308948 (Why is no real title available?)
• scientific article; zbMATH DE number 1743974 (Why is no real title available?)
• scientific article; zbMATH DE number 1903357 (Why is no real title available?)
• scientific article; zbMATH DE number 2192105 (Why is no real title available?)
• On Ramsey number \(R(4,3,3)\) and triangle-free edge-chromatic graphs in three colors
• Satisfiability and computing van der Waerden numbers
• Small Ramsey numbers

Cited in

(17)

• Optimal symmetry breaking for graph problems
• Complete symmetry breaking constraints for the class of uniquely Hamiltonian graphs
• Constraints for symmetry breaking in graph representation
• Computing maximum unavoidable subgraphs using SAT solvers
• Computation of Ramsey numbers by P systems with active membranes
• Optimal-depth sorting networks
• scientific article; zbMATH DE number 1743974 (Why is no real title available?)
• Computation of new diagonal graph Ramsey numbers
• Symbolic moment calculus. II: Why is Ramsey theory sooooo eeeenormously hard?
• New directions in Ramsey theory
• Monk algebras and representability
• Lower bounds for book Ramsey numbers
• A formal proof of R(4,5)=25
• Ramsey numbers through the lenses of polynomial ideals and Nullstellensätze
• Breaking symmetries from a set-covering perspective
• An algebraic perspective on Ramsey numbers
• A nonexistence certificate for projective planes of order ten with weight 15 codewords

Describes a project that uses

Uses Software

• nauty
• CryptoMiniSat
• DRAT-trim

This page was built for publication: Computing the Ramsey number \(R(4,3,3)\) using abstraction and symmetry breaking

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2398438)