Stars of empty simplices (Q6200587)

For a finite set \(X\subset{\mathbb R}^d\) in general position and distinct \(x_1,\dots,x_d\in X\), let \[ \operatorname{deg}_d(x_1,\dots,x_d;X):= \sum_{x_{d+1}\in X\setminus\{x_1,\dots,x_d\}} \1 \{\mathrm{int}\,\mathrm{conv}\{x_1,\dots,x_{d+1}\}\cap X=\emptyset\}.\] The number \(\operatorname{deg}_d(X):= \max \operatorname{deg}_d(x_1,\dots,x_d;X)\), where the \(\max\) is over the \(d\)-element subsets of \(X\), is here studied for random points. A first theorem says the following. Let \(X_n\) be a set of \(n\) independent, uniform random points in a convex body \(K\subset{\mathbb R}^d\). There exists a constant \(c(d,K)>0\) such that \(c(d,K)n\le {\mathbb E}\, \operatorname{deg}_d(X_n)\le n\). (Numerical computations suggest that the optimal constant may be surprisingly large.) Next, let \(N_\Delta(X)\) be the total number of empty simplices defined by \(X\). The authors are able to determine the precise asymptotic behavior of \({\mathbb E}\,N_\Delta(X_n)\) (with \(X_n\) as above) as \(n\to\infty\), and they provide lower and upper bounds for \(N_\Delta(X_n)\) of order \(n^d\) that are independent of \(K\). The number \(\operatorname{deg}_d(X)\) (introduced by Erdös) is generalized, for \(k=1,\dots,d\), to \(\operatorname{deg}_k(X):= \max\operatorname{deg}_k(x_1,\dots,x_k;X)\), where the \(\max\) is over all \(k\)-element subsets \(\{x_1,\dots,x_k\}\subset X\) and \(\operatorname{deg}_k(x_1,\dots,x_k;X)\), for such a subset \(\{x_1,\dots,x_k\}\), is the number of empty simplices defined by \(X\) that contain this subset. For \(k=1\), the following results are obtained (there is a conjecture for general \(k\)). Let \(X_n\) be as above. There are constants \(c(d)\), \(c(d,K)\) such that \(c(d)n^{d-1} \le{\mathbb E}\,\operatorname{deg}_1(X_n)\le c(d,K)n^{d-1}\) for \(d>2\) and \(c(2)n\le {\mathbb E}\,\operatorname{deg}_1(X_n)\le c(2,K)n\ln^{\frac{1}{2}}n\) for \(d=2\).