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

    Identifiers