An Erdős-Szekeres type problem in the plane (Q5932670)

The classical Erdős-Szekeres theorem gives bounds for the minimum number \(g(n)\) such that among any \(g(n)\) points in the plane, no three of them on a line, there are \(n\) points in convex position. The authors consider a variant, asking for the minimum number \(f(n,k)\) such that among any \(f(n,k)\) points in the plane, no three on a line, there are \(n\) points whose convex hull has at least \(k\) vertices. Obviously \(g(k)\leq f(n,k)\leq g(n)\), and from previous work on the Erdős-Szekeres theorem follows that for fixed \(k\), the function \(f(n,k)\) grows only linearly in \(n\). The authors obtain bounds for \(f(n,k)\), they show that \(f(n,4) = \lceil {3\over 2}n\rceil-1\), \(2n-1\leq f(n,5)\leq 7n-23\), and generally \({1\over 2}(k-1)(n-1) + 2^{{1\over 2}k-4} \leq f(n,k)\leq 2kn + 2^{8k}\).