A Discrepancy Problem for Planar Configurations

Yaacov Kupitz and Micha A. Perles asked:

What is the smallest number C such that for every configuration of n points in the plane there is a line containing two or more points from the configuration for which the difference between the number of points on the two sides of the line is at most C?

We will refer to the conjecture that C is bounded as Kupitz-Perles conjecture. It was first conjectured that C=1, but Noga Alon gave an example with C=2. It is not known if C is bounded and, in fact, no example with C>2 is known.

Alon’s example

Kupitz himself proved that , Alon proved that , Perles showed that , and Rom Pinchasi showed that . This is the best known upper bound.  ( is a constant.) Pinchasi’s result asserts something a little stronger: whenever you have n  points in the plane, not all on a line, there is a line containing two or more of the points such that in each open half plane there are at least points. 

The proof uses the method of allowable sequences developed by Eli Goodman and Ricky Pollack. Another famous application of this method is a theorem of Ugnar asserting that 2n points in the plane which are not on the same line determine at least 2n directions. The method of allowable sequences translates various problems in combinatorial geometry into problems about permutations. For example, there is a famous problem about the number of “halving lines” for planar configurations. This problem is one of the “holy grails” of combinatorial geometry.  The translated problem is also quite natural as a problem about permutations.  Consider the permutation on {1,2,3,…,n} which send i to n-i. A reduced representation is a presentation of this permutation as a product of adjacent transpositions. The algebraic question is: What is the maximum number of times that a specific transposition (i,i+1) can occur in such a reduced word?

There are many geometric discrepancy problems which are closer in spirit and in methodology to discrepancy problems in combinatorics and number theory such as the Erdos Discrepancy problem, now under polymath5 attack.  The Kupitz-Perles conjecture seems of a different nature, but I find it very exciting.