Two extensions of the Erős--Szekeres problem

Andreas F. Holmsen, Hossein Nassajian Mojarrad, János Pach, Gábor Tardos

Published 2017-10-31Version 1

According to Suk's breakthrough result on the Erd\H{o}s--Szekeres problem, any point set in general position in the plane, which has no $n$ elements that form the vertex set of a convex $n$-gon, has at most $2^{n+O\left({n^{2/3}\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 $n$ convex bodies in the plane is said to be in convex position if the convex hull of the union of no $n-1$ of its members contains the remaining one. If any three members are in convex position, we say that the family is in {\em 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\'{o}th and by Pach and T\'{o}th, respectively. Let $c(n)$ (and $c'(n)$) denote the smallest positive integer $N$ with the property that any family of $N$ pairwise disjoint convex bodies in general position (resp., $N$ convex bodies in general position, any pair of which share at most two boundary points) has an $n$-membered subfamily in convex position. We show that $c(n)\le c'(n)\leq 2^{n+O\left(\sqrt{n\log n}\right)}$.