An improved upper bound for the Erdős-Szekeres conjecture (Q306509)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | An improved upper bound for the Erdős-Szekeres conjecture |
scientific article |
Statements
An improved upper bound for the Erdős-Szekeres conjecture (English)
0 references
31 August 2016
0 references
Let \(\mathrm{ES}(n)\) denote the least natural number, such that every set of \(\mathrm{ES}(n)\) points in general position in the plane contains \(n\) points in convex position. \textit{P. Erdős} and \textit{G. Szekeres} [Compos. Math. 2, 463--470 (1935; Zbl 0012.27010); Ann. Univ. Sci. Budap. Rolando Eötvös, Sect. Math. 3--4, 53--62 (1961; Zbl 0103.15502)] proved \(2^{n-2} +1 \leq\mathrm{ES}(n)\leq {2n-4\choose n-2}+1\) and conjectured that the lower bound is tight. The paper under review proves the best current upper bound, \(\mathrm{ES}(n)\leq {2n-5\choose n-2} -{2n-8\choose n-3}+2\), which in turn gives \(\limsup_{n\rightarrow \infty} \frac{\mathrm{ES}(n)}{{2n-4\choose n-2}} \leq 7/16\). \textit{S. Norin} and \textit{Y. Yuditsky} [Discrete Comput. Geom. 55, No. 4, 963--971 (2016; Zbl 1351.52018)] reached the same asymptotic upper bound, with a slightly weaker bound.
0 references
Erdős-Szekeres problem
0 references
convex polygons
0 references
Ramsey theory
0 references