The
-set problem is a classic open problem in Combinatorial Geometry, which is considered similar in spirit to incidence problems and to distance problems. While in recent years algebraic techniques led to significant progress in incidence and distance problems, so far none of the new methods were applied to the
-set problem. This post briefly introduces the problem, and describes a way of reducing it to an incidence problem. I hope that it will get someone to think of the
-set problem in an algebraic context and maybe come up with some new observations.
Let
be a set of
points in
, and let
be an integer. A
-set of
is a subset
of
points such that there exists a line that separates
from
. That is,
is on one open half-plane defined by the line, while
is on the other half-plane. The following figure depicts two 5-sets of a set of 12 points.
The
-set problem asks for the maximum number of
-sets that a set of
-points in
can have. As a first silly example, note that the maximum number of 1-sets is exactly
. It is not difficult to show that we may assume that no three points are collinear (specifically, perturbing the point set cannot significantly decrease the number of
-sets).
The number of subsets of
points of
is
, so this is a straightforward upper bound for the maximum number of
sets. However, we can easily obtain a significantly stronger upper bound. Consider a
-set
that is separated by a line
. We translate
until it is incident to a point
and then rotate
around
until it is incident to a second point of
(not necessarily in
). For example, see the figure below. Thus, to find all of the
-sets of
it suffices to consider every line that is incident to two points of
. Since there are
such lines, this is also an upper bound for the number of
-sets.