Tight bounds on the expected number of holes in random point sets. Issue 1 (21st April 2022) - Balko, Martin; Scheucher, Manfred; Valtr, Pavel
Abstract: For integers d ≥ 2 d2 and k ≥ d + 1 kd+1 , a k k ‐hole in a set S S of points in general position in ℝ d 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 ⊆ ℝ d KR^d of unit d d ‐dimensional volume, we study the expected number E H d, k K ( n ) EH_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 E H d, k K ( n ) EH_d, k^K(n) by showing that, for all fixed integers d ≥ 2 d2 and k ≥ d + 1 kd+1 , the number E H d, k K ( n ) EH_d, k^K(n) is at least Ω ( n d ) Ω (n^d) . For some small holes, we even determine the leading constant lim n → ∞ n − d E H d, k K ( n ) _n→ ∞ n^-dEH_d, k^K(n) exactly. We improve the currently best‐known lower bound on lim n → ∞ n − d E H d, d + 1 K ( n ) _n→ ∞ n^-dEH_d, d+1^K(n) by Reitzner and Temesvari (2019). In the plane, we show that the constant lim n → ∞ n − 2 E H 2, k K ( n ) _n→ ∞ n^-2EH_2, k^K(n) is independent of K K for every fixed k ≥ 3 k3 and we compute it exactly for k = 4 k=4 , improving earlier estimates by Fabila‐Monroy, Huemer, and Mitsche and by the authors.