@article{Scheucher_2023, title={A SAT Attack on Erdős-Szekeres Numbers in R^d and the Empty Hexagon Theorem}, volume={2}, url={https://www.cgt-journal.org/index.php/cgt/article/view/12}, DOI={10.57717/cgt.v2i1.12}, abstractNote={<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>}, number={1}, journal={Computing in Geometry and Topology}, author={Scheucher, Manfred}, year={2023}, month={Mar.}, pages={2:1–2:13} }