A SAT attack on the Erdős–Szekeres conjecture. (December 2017)

• Record Type: Journal Article
• Authors: Balko, Martin; Valtr, Pavel
• Is Part Of: European journal of combinatorics. Volume 66(2017)
• Page Start: 13
• Page End: 23
• Publication Date: 2017-12
• Subjects: Combinatorial analysis -- Periodicals; Analyse combinatoire -- Périodiques; Combinatorial analysis; Periodicals; Electronic journals; 511.6
• DOI: 10.1016/j.ejc.2017.06.010
• Languages: English
• ISSNs: 0195-6698

Abstract

Abstract: A classical conjecture of Erdős and Szekeres states that, for every integer k ≥ 2, every set of 2 k − 2 + 1 points in the plane in general position contains k points in convex position. In 2006, Peters and Szekeres introduced the following stronger conjecture: every red-blue coloring of the edges of the ordered complete 3-uniform hypergraph on 2 k − 2 + 1 vertices contains an ordered subhypergraph with k vertices and k − 2 edges, which is a union of a red monotone path and a blue monotone path that are vertex disjoint except for their two common end-vertices. Applying a state of art SAT solver, we refute the conjecture of Peters and Szekeres. We also apply techniques of Erdős, Tuza, and Valtr to refine the Erdős–Szekeres conjecture in order to tackle it with SAT solvers.