# Empty convex polytopes for random point sets

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!

-

Yes, the $2$-dimensional lower bound $\Omega( \frac{\log n}{\log\log n})$ implies a lower bound of that form in all higher dimensions by projecting to a plane.
The projected points are not always uniformly distributed. However, they are for a product region such as a rectangular solid, so the expected largest hole is at least $\Omega( \frac{\log n}{\log\log n})$ for a rectangular solid.
For any two bounded convex $d$-dimensional regions $R$ and $S$, $E(\text{HOL}(R_n)) = \Theta(E(\text{HOL}(S_n)))$ using the notation of theorem $1$ in the Balogh, González-Aguilar, and Salazar paper. In fact, although they state this for convex regions in the plane, they never mention or use that the regions are $2$-dimensional in the proof.
Therefore by the easier side of Balogh, González-Aguilar, and Salazar's result, in dimension at least $2$, the expected largest convex hole in a random set of $n$ points in any bounded convex region is $\Omega(\frac{\log n}{\log\log n} )$. I don't know whether their harder upper bound of the same form also extends to higher dimensions, but I suspect that it does.