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.
-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.
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).
-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.
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.
Advertisements
