I know of the famous results on the Erdős-Szekeres empty convex polygon problem in the plane (the Happy-Ending Problem), and I know that there are higher-dimensional extensions. A great source (albeit a decade out of date) is:
- Morris, W.; Soltan, V. (2000), "The Erdős-Szekeres problem on points in convex position—A survey", Bulletin of the American Mathematical Society 37 (04): 437–458, AMS link.
My query concerns the probability that $n$ random points in $\mathbb{R}^d$ contain an empty $k$-vertex convex polytope. This summer a result was obtained for a planar version of this question:
- József Balogh, Hernán González-Aguilar, Gelasio Salazar, "Large convex holes in random point sets" (arXiv link).
In particular, I wonder if there is a result that there is an empty convex polytope with "approximately" $\Omega(\log n)$ vertices? ("approximately": Perhaps mitigated by $\log \log n$ factors, etc.) If not, what is the best lowerbound that can be claimed? This is primarily a reference request. Thanks!