Some Erdős-Szekeres type results about points in space (Q1335532)

Let \(f(n,d)\) and \(g(n,d)\) denote the least integer \(k \geq n\) such that any set of at least \(k\) points in \(E^ d\) contains a subset of \(n\) points which are the vertices of a convex polytope for \(f\), and for \(g\) we demand the additional condition that the polytope be empty (its interior contains no points of the set). Thus \(f(n,d) \leq g(n,d)\). An old result of Erdős and Szekeres (generalized by Grünbaum) states that \(f(n,d)\) is finite for all \(n\) and \(d\). However, \(g(n,d)\) exists only up to \(n = 6\) for \(d = 2\). Its domain of existence is not known for all \(d\); \textit{P. Valtr} [Discrete Math. 108, No. 1-3, 115-124 (1992; Zbl 0766.52003)] proved that it exists for \(n \leq 2d + 1\), and does not for \(n > 2^{d - 1}(N(d - 1) + 1)\), where \(N(d - 1)\) is the product of the smallest \(d - 1\) primes. The authors prove that \(f(n,d)\) is also the smallest \(k \geq n\) such that any set of \(k\) points spanning \(E^ d\) contain \(n\) points on the boundary of the convex hull whose affine hull is also \(E^ d\). They also prove that, for \(d \geq 2\) and \(1 \leq k \leq \lfloor d/2 \rfloor + 1\), we have \(g(d + k,d) \leq d + 2k - 1\). So far, we thus know that \(f(d + 1) = g(d + 1) = d + 1\) (trivial), \(f(n,2) = g(n,2) = d + 3\) (well-known for \(f\), consequence of the above for \(g\)), and that \(g(d + 3, d) \leq d + 5\). For the latter, the following tight results are also proved: \(f(6,3) = g(6,3) = 9\), \(g(7,4) = 9\).