论文标题
从较少点的凸多型
Convex polytopes from fewer points
论文作者
论文摘要
令$ es_ {d}（n）$为最小的整数，以便在$ \ mathbb {r}^{d}中的任何集合$ es_ {d}（n）$点在一般位置中包含$ n $ n $点的convex位置。 1960年，Erdős和Szekeres表明$ ES_ {2}（n）\ geq 2^{n-2} + 1 $保持，并著名地猜想他们的构建是最佳的。这几乎是由Suk在2017年解决的，他表明$ es_ {2}（n）\ leq 2^{n+o（n）} $。在本文中，我们证明了$$ es_ {d}（n）= 2^{o（n）} $$所有$ d \ geq 3 $都保留。特别是，这确定在较高的维度上，与$ n $顶点相比，与飞机中需要多少相比，要确保在$ n $顶点上存在凸层。
Let $ES_{d}(n)$ be the smallest integer such that any set of $ES_{d}(n)$ points in $\mathbb{R}^{d}$ in general position contains $n$ points in convex position. In 1960, Erdős and Szekeres showed that $ES_{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 $ES_{2}(n) \leq 2^{n+o(n)}$. In this paper, we prove that $$ES_{d}(n) = 2^{o(n)}$$ holds for all $d \geq 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.
