Convex polytopes from fewer points

Abstract

Let $E{S}_d(n)$ be the smallest integer such that any set of $E{S}_d(n)$ points in ${\mathbb{R}}^d$ in general position contains $n$ points in convex position. In 1960, Erdős and Szekeres showed that $E{S}_2(n)\ge 2^{n-2}+1$ holds, and famously conjectured that their construction is optimal. This was nearly settled by Suk in 2017, who showed that $E{S}_2(n)\le 2^{n+o(n)}$. In this paper, we prove that $$E{S}_d(n)=2^{o(n)}$$ holds for all $d\ge 3$. In particular, this establishes that, in higher dimensions, substantially fewer points are needed in order to ensure the presence of a convex polytope on $n$ vertices, compared to how many are required in the plane.