ON THE EXPECTED NUMBER OF K-SETS

Given a set S of n points in R(d), a subset X of size d is called a k-simplex if the hyperplane aff(X) has exactly k points on one side. We study E(d)(k, n), the expected number of k-simplices when S is a random sample of n-points from a probability distribution P on R(d). When P is spherically symmetric we prove that E(d)(k, n) less-than-or-equal-to cn(d-1). When P is uniform on a convex body K subset-of R2 we prove that E2(k, n) is asymptotically linear in the range cn less-than-or-equal-to k less-than-or-equal-to n/2 and when k is constant it is asymptotically the expected number of vertices on the convex hull of S. Finally, we construct a distribution P on R2 for which E2((n - 2)/2, n) is cn log n.