The Erdos-Szekeres problem on points in convex position – a survey

By W. Morris, V. Soltan. 2000

139 citations recorded by the source corpus.

In 1935 Erdős and Szekeres proved that for any integer n ≥ 3 there exists a smallest positive integer N(n) such that any set of at least N(n) points in general position in the plane contains n points that are the vertices of a convex n-gon. They also posed the problem to determine the value of N(n) and conjectured that N(n) = 2n−2 + 1 for all n ≥ 3. Despite the efforts of many mathematicians, the Erdős-Szekeres problem is still far from being solved. This paper surveys the known results and questions related to the Erdős-Szekeres problem in the plane and higher dimensions, as well as its generalizations for the cases of families of convex bodies and the abstract convexity setting.

Subfields: Computational Theory and Mathematics, Discrete Mathematics and Combinatorics

View Paper: https://www.semanticscholar.org/paper/f32acdc886b303e1162d482d759bf3516eeec9fd