Notes on the 33-point Erdős--Szekeres problem
Fuente:
arXiv
Salvato in:
| Autore principale: | |
|---|---|
| Natura: | Preprint |
| Pubblicazione: |
2025
|
| Soggetti: | |
| Accesso online: | |
| Tags: |
Aggiungi Tag
Nessun Tag, puoi essere il primo ad aggiungerne!!
|
| _version_ | 1866911346658902016 |
|---|---|
| author | Dumitru, Bogdan |
| author_facet | Dumitru, Bogdan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2512_24061 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Notes on the 33-point Erdős--Szekeres problem Dumitru, Bogdan Combinatorics Computational Geometry 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. |
| title | Notes on the 33-point Erdős--Szekeres problem |
| topic | Combinatorics Computational Geometry |
| url | https://arxiv.org/abs/2512.24061 |