TY - JOUR
AU - Scheucher, Manfred
PY - 2023/03/20
Y2 - 2024/11/07
TI - A SAT Attack on Erdős-Szekeres Numbers in R^d and the Empty Hexagon Theorem
JF - Computing in Geometry and Topology
JA - CompGeomTop
VL - 2
IS - 1
SE - Original Research Articles
DO - 10.57717/cgt.v2i1.12
UR - https://www.cgt-journal.org/index.php/cgt/article/view/12
SP - 2:1-2:13
AB - <p> A famous result by Erdős and Szekeres (1935) asserts that, for all k, d in N, there is a smallest integer n = g<sup>(d)</sup>(k) such that every set of at least n points in R<sup>d</sup> in general position contains a k-gon, that is, a subset of k points in convex position.<br />We present a SAT model based on acyclic chirotopes (oriented matroids) to investigate Erdős-Szekeres numbers in small dimensions. SAT instances are solved using modern SAT solvers and unsatisfiability results are verified using DRAT certificates.<br />We show g<sup>(3)</sup>(7) = 13, g<sup>(4)</sup>(8) ≤ 13, and g<sup>(5)</sup>(9) ≤ 13, which are the first improvements for decades. For the setting of k-holes (i.e., k-gons with no other points in the convex hull), where h<sup>(d)</sup>(k) denotes the smallest integer n such that every set of at least n points in R<sup>d</sup> in general position contains a k-hole, we show h<sup>(3)</sup>(7) ≤ 14, h<sup>(4)</sup>(8) ≤ 13, and h<sup>(5)</sup>(9) ≤ 13. All obtained bounds are sharp in the setting of acyclic chirotopes and we conjecture them to be sharp also in the original setting of point sets.<br />Last but not least, we verify all previously known bounds and, in particular, we present the first computer-assisted proof for the existence of 6-holes in sufficiently planar point sets by verifying Gerken's estimate h<sup>(2)</sup>(6) ≤ g<sup>(2)</sup>(9).</p>
ER -