The Erdős–Szekeres conjecture revisited
Summary
No summary yet. VIRAT can read this paper and write a plain-language summary of its aim, methods, key findings and limitations.
Summarise with VIRAT Free to try with your Science Catalogs account.Abstract
The famous and still open Erdős–Szekeres Conjecture from 1935 states that every set of at least 2 k − 2 + 1 points in the plane with no three being collinear contains k points in convex position , that is, k points that are vertices of a convex polygon. In this paper, we revisit this conjecture and show several new related results. First, we prove a relaxed version of the Erdős–Szekeres Conjecture by showing that every set of at least 2 k − 2 + 1 points in the plane with no three being collinear contains a split k-gon , a relaxation of k -tuple of points in convex position. Moreover, we show that this is tight, showing that the value 2 k − 2 + 1 from the Erdős–Szekeres Conjecture is exactly the right threshold for split k -gons. We obtain an analogous relaxation in a much more general setting of ordered 3-uniform hypergraphs, where we also show that, perhaps surprisingly, a corresponding generalization of the Erdős–Szekeres Conjecture is not true. Finally, we prove the Erdős–Szekeres Conjecture for so-called decomposable sets and provide new constructions of sets of 2 k − 2 points without k points in convex position, generalizing all previously known constructions of such point sets and allowing us to computationally tackle the Erdős–Szekeres Conjecture for large values of k .
Fields of Study & Subjects
Advanced Combinatorial Mathematics
Limits and Structures in Graph Theory
Computational Geometry and Mesh Generation
Publication details
- Journal / source
- Journal of Combinatorial Theory Series A
- Volume
- 222
- Pages
- 106195–106195
- Publication date
- 30 March 2026
- Language
- EN