Interior points in the Erdős-Szekeres theorems (Q2435979)

The author investigates the following generalization of the famous Erdős-Szekeres problem. Let \(n\geq 3\) and \(k\geq 0\) be integers. What is the minimal positive integer \(h(n,k)\) with the property that every planar point set of cardinality at least \(h(n,k)\), whose elements are in general position, contains the vertices of a convex \(n\)-gon that has at most \(k\) other points of the set in its interior? In particular, if \(k\geq n-k\), then \(g(n)=h(n,k)\) is the minimal number such that any set of points of cardinality at least \(g(n)\) in the plane in general position contains the vertices of a convex \(n\)-gon; finding \(g(n)\) is the subject of the original Erdős-Szekeres problem. The case \(k=0\) corresponds to another version of the Erdős-Szekeres problem which seeks the minimum number \(h(n)=h(n,0)\) with the property that from any planar point set of cardinality at least \(h(n)\) in general position one can always select the vertices of an empty convex \(n\)-gon. It was proved by Horton in 1983 that \(h(n)\) does not exist for \(n\geq 7\). For \(n\geq 7\), let \(\underline{k}(n)\) be the largest integer for which \(h(n,k)\) does not exist. From the definition it follows that \(g(n)\leq h(n,k)\) for all \(k\geq 0\) and \(h(n,k)\) is a decreasing function of \(k\) (when \(h(k,n)\) exists). Let \(\overline{k}(n)\) denote the integer (if such a number exists) with the propeties that \(h(n, \overline{k}(n)) > g(n)\) and \(h(n,k)=g(n)\) for \(k > \overline{k}(n)\). The main results of the paper include a signifcantly improved lower estimate of \(\underline{k}(n)\) and upper estimates related to \(\overline{k}(n)\).