Notes on the 33-point Erdős--Szekeres problem
By: Bogdan Dumitru
The determination of $ES(7)$ is the first open case of the planar Erdős--Szekeres problem, where the general conjecture predicts $ES(7)=33$. We present a SAT encoding for the 33-point case based on triple-orientation variables and a 4-set convexity criterion for excluding convex 7-gons, together with convex-layer anchoring constraints. The framework yields UNSAT certificates for a collection of anchored subfamilies. We also report pronounced runtime variability across configurations, including heavy-tailed behavior that currently dominates the computational effort and motivates further encoding refinements.
Similar Papers
A complete solution of the Erdős-Kleitman matching problem for $n\le 3s$
Combinatorics
Finds the biggest group of lists with no $s$ empty lists.
Verified Certificates via SAT and Computer Algebra Systems for the Ramsey $R(3, 8)$ and $R(3, 9)$ Problems
Logic in Computer Science
Proves math puzzles faster and more reliably.
Automated Symmetric Constructions in Discrete Geometry
Discrete Mathematics
Finds new, beautiful math shapes faster.