JournalsjemsVol. 22, No. 12pp. 3981–3995

Two extensions of the Erdős–Szekeres problem

  • Andreas F. Holmsen

    Korea Advanced Institute of Science and Technology (KAIST), Daejeon, Republic of Korea
  • Hossein Nassajian Mojarrad

    New York University, USA
  • János Pach

    Ecole Polytechnique Fédérale de Lausanne, Switzerland
  • Gábor Tardos

    Rényi Institute and Central European University, Budapest, Hungary
Two extensions of the Erdős–Szekeres problem cover
Download PDF

A subscription is required to access this article.


According to Suk's breakthrough result on the Erdős–Szekeres problem, any point set in general position in the plane, which has no nn elements that form the vertex set of a convex nn-gon, has at most 2n+O(n2/3logn)2^{n+O\left({n^{2/3}\mathrm log n}\right)} points. We strengthen this theorem in two ways. First, we show that the result generalizes to convexity structures induced by pseudoline arrangements. Second, we improve the error term.

A family of nn convex bodies in the plane is said to be in convex position if the convex hull of the union of no n1n-1 of its members contains the remaining one. If any three members are in convex position, we say that the family is in general position. Combining our results with a theorem of Dobbins, Holmsen, and Hubard, we significantly improve the best known upper bounds on the following two functions, introduced by Bisztriczky and Fejes Tóth and by Pach and Tóth, respectively. Let c(n)c(n) (and c(n)c'(n)) denote the smallest positive integer NN with the property that any family of NN pairwise disjoint convex bodies in general position (resp., NN convex bodies in general position, any pair of which share at most two boundary points) has an nn-membered subfamily in convex position. We show that c(n)c(n)2n+O(nlogn)c(n)\leq c'(n)\leq 2^{n+O\left(\sqrt{n\mathrm log n}\right)}.

Cite this article

Andreas F. Holmsen, Hossein Nassajian Mojarrad, János Pach, Gábor Tardos, Two extensions of the Erdős–Szekeres problem. J. Eur. Math. Soc. 22 (2020), no. 12, pp. 3981–3995

DOI 10.4171/JEMS/1000