Convex polytopes from fewer points

arXiv2208.04878MaRDI QIDQ6407423FDOQ6407423

Authors: Cosmin Pohoata, D. D. Zakharov 

Publication date: 9 August 2022

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, ErdH{o}s and Szekeres showed that $E{S}_2(n)geq{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)leq{2}^{n+o(n)}$. In this paper, we prove that ${\displaystyle }$ES_{d}(n) = 2^{o(n)}${\displaystyle }$ holds for all $dgeq3$. 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.

This page was built for publication: Convex polytopes from fewer points

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6407423)