On a conjecture of Erd\H{o}s and Szekeres

MaRDI QIDQ6262170zbMATH OpenFDO

Authors Georgios Vlachos

Publication date 28 May 2015

Abstract: Let f(n) denote the smallest positive integer such that every set of $f(n)$ points in general position in the Euclidean plane contains a convex n-gon. In a seminal paper published in 1935, ErdH{o}s and Szekeres proved that f(n) exists and provided an upper bound. In 1961, they also proved a lower bound, which they conjectured is optimal. Their bounds are: $2^{n-2}+1leqf(n)leq2n-4choosen-2+1$. Since then, the upper bound has been improved by rougly a factor of 2, to $f(n)leq2n-5choosen-2+1$. In the current paper, we further improve the upper bound by proving that: ${\displaystyle }$ limsuplimits_{n ightarrow infty} frac{f(n)}{{2n-5 choose n-2}} leq frac{29}{32}${\displaystyle }$

This page was built for publication: On a conjecture of Erd\H{o}s and Szekeres

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