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

For integersd ≥ 2 $$ d\ge 2 $$ andk ≥ d + 1 $$ k\ge d+1 $$ , ak $$ k $$ ‐hole in a setS $$ S $$ of points in general position inℝ d$$ {\mathbb{R}}^d $$ is ak $$ k $$ ‐tuple of points fromS $$ S $$ in convex position such that the interior of their convex hull does not contain any point fromS $$ S $$ . For a convex bodyK ⊆ ℝ d$$ K\subseteq {\mathbb{R}}^d $$ of unitd $$ d $$ ‐dimensional volume, we study the expected numberE H d , k K ( n ) $$ E{H}_{d,k}^K(n) $$ ofk $$ k $$ ‐holes in a set ofn $$ n $$ points drawn uniformly and independently at random fromK $$ K $$ . We prove an asymptotically tight lower bound onE H d , k K ( n ) $$ E{H}_{d,k}^K(n) $$ by showing that, for all fixed integersd ≥ 2 $$ d\ge 2 $$ andk ≥ d + 1 $$ k\ge d+1 $$ , the numberE H d , k K ( n ) $$ E{H}_{d,k}^K(n) $$ is at leastΩ ( n d ) $$ \Omega \left({n}^d\right) $$ . For some small holes, we even determine the leading constantlim n → ∞n − d E H d , k K ( n ) $$ {\lim}_{n\to \infty }{n}^{-d}E{H}_{d,k}^K(n) $$ exactly. We improve the currently best‐known lower bound onlim n → ∞n − d E H d , d + 1 K ( 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 constantlim n → ∞n − 2 E H 2 , k K ( n ) $$ {\lim}_{n\to \infty }{n}^{-2}E{H}_{2,k}^K(n) $$ is independent ofK $$ K $$ for every fixedk ≥ 3 $$ k\ge 3 $$ and we compute it exactly fork = 4 $$ k=4 $$ , improving earlier estimates by Fabila‐Monroy, Huemer, and Mitsche and by the authors.