The Erdős–Szekeres conjecture revisited

Read full text Summarise with VIRAT
Authors: Jineon Baek, Martin Balko
Cited by: 0
References: 23

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