On the Erdos-Szekeres convex polygon problem
On the Erdos-Szekeres convex polygon problem
复制标题
关于Erdos-Szekeres凸多边形问题
DOI：
--
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
Andrew Suk
中科院分区：
文献类型：
--
作者：
Andrew Suk
令$ es（n）$为最小的整数，以使飞机上的任何$ es（n）$点一般位置都包含$ n $点的凸点位置。在1935年的开创性论文中，Erdos和Szekeres表明$ es（n）\ leq {2n -4 \ select n -2} + 1 = 4^{n -o（n）} $。 1960年，他们表明$ es（n）\ geq 2^{n-2} + 1 $，并猜想这是最佳的。在本文中，我们几乎通过证明$ es（n）= 2^{n +o（n）} $来解决Erdos-Szekeres的猜想。
Let $ES(n)$ be the smallest integer such that any set of $ES(n)$ points in the plane in general position contains $n$ points in convex position. In their seminal 1935 paper, Erdos and Szekeres showed that $ES(n) \leq {2n - 4\choose n-2} + 1 = 4^{n -o(n)}$. In 1960, they showed that $ES(n) \geq 2^{n-2} + 1$ and conjectured this to be optimal. In this paper, we nearly settle the Erdos-Szekeres conjecture by showing that $ES(n) =2^{n +o(n)}$.