Algebraic k-sets and generally neighborly embeddings
share
Given a set S of n points in R^d, a k-set is a subset of k points of S that can be strictly separated by a hyperplane from the remaining n-k points. Similarly, one may consider k-facets, which are hyperplanes that pass through d points of S and have k points on one side. A notorious open problem is to determine the asymptotics of the maximum number of k-sets. In this paper we study a variation on the k-set/k-facet problem with hyperplanes replaced by algebraic surfaces belonging to certain families. We demonstrate how one may translate bounds for the original problem to bounds for the algebraic variation. In stark contrast to the original k-set/k-facet problem, there are some natural families of algebraic curves for which the number of k-facets can be counted exactly. For example, we show that the number of halving conic sections for any set of 2n+5 points in general position in the plane is 2n+22^2. To understand the limits of our argument we study a class of maps we call generally neighborly embeddings, which map generic point sets into neighborly position.
READ FULL TEXT