Halving lines and k-sets
Let be a set of points in general position, meaning that no three are collinear. A -set is a subset with that can be strictly separated from by a line: the two subsets lie in opposite open half-planes. Write for the number of distinct -sets of , and, for , define
where the maximum is over planar sets in general position. The planar k-set question is to determine these maxima, particularly their asymptotic growth as and vary. Wagner (2007)
For even , a halving line of is a line through two points of with exactly of the other points in each open half-plane. Let be the maximum number of distinct halving lines over such sets . More generally, for fixed and , let be the maximum number of distinct affine hyperplanes spanned by points of a general-position set for which the two open sides contain numbers of the remaining points differing by at most one. Thus the side counts are equal when is even and are the two nearest integers when it is odd. The questions are to determine these extrema, or their asymptotic orders; in particular, the planar halving-line problem is the even- middle case of the broader k-set problem. Wagner (2007)
Background
The extremum depends on the point configuration, not just on its size: even for four points, different configurations can have different numbers of equal partitions by a line. The planar halving question was raised in the early 1970s; Wagner attributes the special case to an unpublished question of Simmons. In the broader formulation, a separating hyperplane defines a k-set, while a hyperplane spanned by points of the set leads to the related notion of a k-facet. In the plane, the number of k-sets equals the number of suitably indexed oriented k-edges, and these edge counts correspond in the dual arrangement of lines to counts of faces on a level. This connection makes bounds on arrangement levels useful for studying the extremal counts. Wagner (2007)
The earliest bounds described in this history already show the challenge of the middle level. Straus obtained a lower bound of order for the planar halving case, while Lovász proved an upper bound. The later bounds for general planar levels were developed by Erdős, Lovász, Simmons, and Straus. Estimates for halving facets also have consequences for other levels: in fixed dimension, an improved upper bound at the middle level can be transferred to bounds that depend on the level parameter. Wagner (2007)
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 1
Claimed by OpenAI. Claims absolute constants epsilon>0,C,n_0 such that every even n>=n_0 planar point set with no three collinear has at most C n^(4/3-epsilon) unordered halving pairs. This gives an improved upper bound for the maximum-halving-lines problem; it does not determine the sharp maximum or establish n^(1+eta) bounds for every eta>0. The proof supplies no effective numerical exponent or constants.See full solution
Claimed by OpenAI.
Claims absolute constants epsilon>0,C,n_0 such that every even n>=n_0 planar point set with no three collinear has at most C n^(4/3-epsilon) unordered halving pairs. This gives an improved upper bound for the maximum-halving-lines problem; it does not determine the sharp maximum or establish n^(1+eta) bounds for every eta>0. The proof supplies no effective numerical exponent or constants.
GitHub repository: https://github.com/openai/math
- OpenAI-183-01-A-power-saving-for-planar-halving-lines.pdfOpen