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.
The current best upper bound for the maximum number of -sets is . This bound was derived by Dey about 20 years ago. Similarly to the pre-algebraic era in incidence and distance problems, this bound was obtained by using the crossing lemma. In the other direction, Tóth constructed a set of points and -sets. This result was published in 2001, and the problem seems to have been stuck since then (although there are many later work on variants of the problem).
A dual problem. The -set problem has an interesting dual formulation. Consider only the -sets that are separated by a line such that is above the line (the case of -sets below the separating line can be handled symmetrically). Given a point , we define the dual line by the equation . Given a line defined by , we define the dual point as . Note that is incident to if and only if is incident to . Indeed, both cases occur if and only if . By replacing the equality with , we get that is above if and only if is above .
Consider the set of lines
Let be a line that has a -set above it and below it. Let be the set of lines dual to the points of . Then the point is above the lines of and below the lines of . That is, a point of is dual to a line that separates a -set if and only if it has exactly lines of below it.
As stated above, it suffices to consider -sets where the separating line is incident to at least two points of . The dual statement says that it suffices to bound the points that are incident to at least two lines of . That is, the -set problem was reduced to the following.
Problem 1. Let be a set of lines in . Find an upper bound for the number of points of that are incident to at least two lines of and have exactly or lines of above them.
Problem 1 asks for the complexity of the ‘th level in an arrangement of lines.
Algebraic techniques. How can the -set problem be studied using algebraic techniques? I will now present one such connection that I recently noticed. I suspect that stronger and more “natural” connections might exist, so I hope that you will ignore the following and try to come up with a better approach.
In a recent paper by Fox, Pach, Suk, Zahl, and myself, we studied incidences with semi-algebraic objects. The following is a simple corollary of a theorem from that paper.
Corollary 2. Let be a set of points in the plane and let be a set of open half-planes, both in . Let be a positive integer (which may depend on and ) such that the incidence graph of contains no copy of . Then
We can reduce the -set problem to a similar incidence problem. Recall that we are given a set of points in and can think of every -set as an open half-plane that contains exactly points. The intersection of two such half-planes contains at most common points of . That is, the number of -sets is upper bounded by the number of -rich half-planes when assuming that the incidence graph contains no copy of . By a duality argument as described above, we get to the problem of bounding the number of -rich points when there is no in the incidence graph.
While Corollary 2 provides a nice bound for incidences with half-planes when no exists, I could not obtain any non-trivial bound for the number of -rich points. Joshua Zahl pointed out one reason for why this is difficult to do: The number of -rich points can be infinite, and our current incidence tools are not delicate enough to distinguish between -rich and -rich points. Moreover, it is possible that the two problems are not asymptotically equivalent, and the maximum number of rich points is larger than the maximum number of -sets. If you have additional observations concerning this problem, I will be happy to hear about them.