On the number of linearly separable subsets of finite sets in \(\mathbb{R}^n\) (Q1380812)

Given a finite set \(X\) of points in general position in \(\mathbb{R}^n\), one may ask which subsets can be separated from the others by a hyperplane (or, equivalently, characterized by a linear inequality). Let \(\Gamma_k\), \(k=1,2, \dots\), be the number of separable \(k\)-element subsets of \(X\). A 1965 theorem of T. M. Cover gives the sum of the \(\Gamma_k\) as a function; but it would be useful to know more about the individual values. However, even for a set in convex general position -- that is, in general position with every point extreme in the convex hull of the set -- this is a deep problem, akin to classifying the \(n\)-dimensional polytopes with \(m\) vertices. (In particular, for such a set, a separable subset with \(n\) or fewer elements is a \((n-1)\)-face of the convex hull.) In this paper, Gulliksen and Hole show (using a rather subtle deformation argument) that in \(\mathbb{R}^3\), for all \(k\) and \(m\), \(\Gamma_k\) is invariant over all \(m\)-element sets in convex general position, and hence always takes the value, \(2k(m-k)- m+2\), that it has for the cyclic polytopes. By a similar argument, they also show that if \(n\) is odd, the alternating sum \(\Sigma (-1)^k \Gamma_k\) is invariant over all subsets of \(R^n\) in general position, and always equal to 0. Examples are given to show that the \(\Gamma_k\) are not invariant in higher-dimensional spaces, and that the alternating sum is not always invariant in even-dimensional spaces.