 |
Computing the Ramsey number R(4,3,3) using abstraction and symmetry breaking
Michael Codish, Michael Frank, Avraham Itzhakov and Alice Miller
Constraints;
21 (3): 375--393,
2016
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 abstraction and 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 of (3,3,3;13) colorings consisting of 78,892 Ramsey colorings.Available: bibtex entry
Related sites: from the arXiv from Springer
Michael Codish
The Department of Computer Science
Ben-Gurion University of the Negev
PoB 653, Beer-Sheva, 84105, Israel
mcodish@cs.bgu.ac.il