Tight bounds on the expected number of holes in random point sets

For integers d >= 2$$ d\ge 2 $$ and k >= d+1$$ k\ge d+1 $$, a k$$ k $$-hole in a set S$$ S $$ of points in general position in Double-struck capital Rd$$ {\mathbb{R}}<^>d $$ is a k$$ k $$-tuple of points from S$$ S $$ in convex position such that the interior of their convex hull does not contain any point from S$$ S $$. For a convex body K subset of Double-struck capital Rd$$ K\subseteq {\mathbb{R}}<^>d $$ of unit d$$ d $$-dimensional volume, we study the expected number EHd,kK(n)$$ E{H}_{d,k}<^>K(n) $$ of k$$ k $$-holes in a set of n$$ n $$ points drawn uniformly and independently at random from K$$ K $$. We prove an asymptotically tight lower bound on EHd,kK(n)$$ E{H}_{d,k}<^>K(n) $$ by showing that, for all fixed integers d >= 2$$ d\ge 2 $$ and k >= d+1$$ k\ge d+1 $$, the number EHd,kK(n)$$ E{H}_{d,k}<^>K(n) $$ is at least omega(nd)$$ \Omega \left({n}<^>d\right) $$. For some small holes, we even determine the leading constant limn ->infinity n-dEHd,kK(n)$$ {\lim}_{n\to \infty }{n}<^>{-d}E{H}_{d,k}<^>K(n) $$ exactly. We improve the currently best-known lower bound on limn ->infinity n-dEHd,d+1K(n)$$ {\lim}_{n\to \infty }{n}<^>{-d}E{H}_{d,d+1}<^>K(n) $$ by Reitzner and Temesvari (2019). In the plane, we show that the constant limn ->infinity n-2EH2,kK(n)$$ {\lim}_{n\to \infty }{n}<^>{-2}E{H}_{2,k}<^>K(n) $$ is independent of K$$ K $$ for every fixed k >= 3$$ k\ge 3 $$ and we compute it exactly for k=4$$ k=4 $$, improving earlier estimates by Fabila-Monroy, Huemer, and Mitsche and by the authors.

Automated summary

This paper investigates the number of k-holes in a set of points randomly drawn from a convex body, and provides asymptotic lower bounds and exact values for certain cases. Additionally, it improves upon existing research in specific scenarios.