Erdős–Szekeres for n = 7: does every set of 33 points in general position contain a convex heptagon?
Difficulty 45: a finite, fully specified question whose expected answer is yes, with a visible route (symmetry breaking plus large-scale certified SAT), but ES(6) was already a major 2006 computation and the 33-point instance is far larger; this places it below r(4,t) (55) and cap sets (58) and far below the infinite Hadwiger–Nelson problem (79). Application value 1.8: none beyond SAT benchmarking. Leverage 14: it would confirm one more case without implying the general conjecture, the lowest in the area.
The problem
Does every set of 33 scattered points contain seven that form a convex heptagon? Known for up to 6; seven is open.
- 1Scatter points, no three in a line
- 2Guess: 2^(n-2)+1 points force n-gon
- 3Verified for 4, 5 and 6 corners
- 4Seven corners (33 points) is open
Definition. Let be the least such that every set of points in the plane in general position (no three collinear) contains points in convex position (the vertices of a convex -gon). Erdős and Szekeres proved in 1935 that is finite and conjectured . In 1960–61 they gave a construction showing , by explicit sets of points with no convex -gon.
Path to understanding
foundations → problemThe research entries this problem rests on, in the order to read them. Each links to its explainer.
- Start with
- Step 2
- Step 3
- SAT solving (CDCL)Algorithm
- Step 4
- Extremal and probabilistic combinatoricsTheory · host
- Then
- Erdős–Szekeres for n = 7: does every set of 33 points in general position contain a convex heptagon?The problem
State of the art
ES(5)=9 was proved by Makai (unpublished; first published proof by Kalbfleisch, Kalbfleisch and Stanton, 1970), and ES(6)=17 by Szekeres and Peters (ANZIAM J. 48, 2006) through an exhaustive computer search; it has since been re-verified by SAT-based and formal methods (Scheucher; Marić in Isabelle/HOL). For asymptotics, Suk (2016; JAMS 2017) proved ES(n) = 2^{n+O(n^{2/3} log n)}, and Holmsen, Mojarrad, Pach and Tardos (arXiv:1710.11415) improved the error term to O(√(n log n)) in the exponent. For n = 7 only partial computational results exist: a December 2025 single-author preprint (Dumitru, arXiv:2512.24061, unrefereed) gives a SAT encoding of the 33-point case with triple-orientation variables, a 4-set convexity criterion and convex-layer anchoring, and obtains UNSAT certificates only for anchored subfamilies, reporting heavy-tailed solver runtimes. No complete resolution, human or AI-produced, was found as of 2026-10-16.
Realistic applications
None practical. Methodologically it is a benchmark for SAT solving with symmetry breaking and for proof-certificate checking in finite geometry.
What counts as solved
A complete certified proof (e.g. a DRAT/LRAT certificate of unsatisfiability of the full 33-point encoding, checked by a verified checker) that no 33-point set avoids a convex 7-gon, or an explicit counterexample set of 33 points. Partial subfamily certificates do not count.
How it gets verified
Bound / recordA numeric bound or record checked from a certificate or recomputation.
Quantity: whether 33 points in general position always contain a convex heptagon, i.e. ES(7) = 33. Resolution is a complete certificate: a DRAT/LRAT proof of unsatisfiability of the full 33-point SAT encoding checked by a verified checker, or an explicit set of 33 points in general position with no convex heptagon; partial subfamily certificates do not count. The Lean statement of the general conjecture is Erdos107.erdos_107 (f(n) = 2^(n−2) + 1) in ErdosProblems/107.lean (Formal Conjectures pinned at commit e754a78 (17 October 2026)); its n = 7 instance is the target, and the correspondence between the SAT encoding and that statement must be reviewed or proved.
Claims under verification
+ add a claimNo claimed results on the Verification board for this problem yet.
Where the work is
Mostly a computation, but cracking the instance needs better symmetry breaking and encodings (theory), plus a verified proof-checking pipeline.
Bottlenecks
ranked by votes- #1ComputeHeavy-tailed SAT runtimes on the full encoding
The 33-point instance has a very large number of orientation clauses and a large symmetry group; reported runtimes on anchored subcases vary by orders of magnitude, so a complete case split is not yet feasible.
Community grades
Sign in to add your own grade.
Connected problems
Progress
- Dec 30, 2025SAT encoding of the 33-point case (unrefereed preprint)source
UNSAT certificates for anchored subfamilies only; the full case remains open.
- Oct 31, 2017Error term improved to O(√(n log n))source
Holmsen, Mojarrad, Pach and Tardos sharpen Suk's exponent.
- Apr 29, 2016Suk proves ES(n) = 2^{n+o(n)}source
First near-matching upper bound, with error term O(n^(2/3) log n) in the exponent.
- Oct 1, 2006ES(6) = 17source
Szekeres and Peters settle the hexagon case by exhaustive computer search (ANZIAM J. 48; month approximate, day set to the first).