On the Erdös-Szekeres problem (Q2377533): Difference between revisions

A classic theorem of Erdős and Szekeres asserts that for every \(n\geq 3\), there exists a smallest number \(g(n)\) such that any \(g(n)\) points in the plane in general position (i.e no 3 collinear) contain the vertices of a convex \(n\)-gon. The exact values of \(g(n)\) are known up to \(n=5\) or perhaps \(n=6\), which result is unpublished. Erdős and Szekeres also defined a smallest number \(h(n)\) such that any \(h(n)\) points in the plane in general position (i.e no 3 collinear) contain the vertices of a convex \(n\)-gon, which contains none of the \(h(n)\) points in its interior. Values of \(h(n)\) have been determined for \(n\leq 5\) and it turned out that \(h(n)\) does not exist for \(n\geq 7\). In 2006 [\textit{T. Gerken}, Twentieth anniversary volume: Discrete and computational geometry. New York, NY: Springer. 220--253 (2008; Zbl 1169.52006)], showed the existence of \(h(6)\). The paper under review gives improved upper bounds on \(h(6)\): \(h(6)\leq \max \{g(8), 400\}\leq 463\).