A SAT attack on higher dimensional Erdős–Szekeres numbers
share
A famous result by Erdős and Szekeres (1935) asserts that, for every k,d ∈ℕ, there is a smallest integer n = g^(d)(k), such that every set of at least n points in ℝ^d in general position contains a k-gon, i.e., a subset of k points which is in convex position. We present a SAT model for higher dimensional point sets which is based on chirotopes, and use modern SAT solvers to investigate Erdős–Szekeres numbers in dimensions d=3,4,5. We show g^(3)(7) ≤ 13, g^(4)(8) ≤ 13, and g^(5)(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^(d)(k) denotes the minimum number n such that every set of at least n points in ℝ^d in general position contains a k-hole, we show h^(3)(7) ≤ 14, h^(4)(8) ≤ 13, and h^(5)(9) ≤ 13. Moreover, all obtained bounds are sharp in the setting of chirotopes and we conjecture them to be sharp also in the original setting of point sets.
READ FULL TEXT