Everywhere Unbalanced Configurations by David Conlon and Jeck Lim

Source: Cheerful news in difficult times: David Conlon and Jeck Lim settled Kupitz’s planar discrepancy problem for pseudolines by Gil Kalai

Everywhere unbalanced configurations, by David Conlon and Jeck Lim

Some years ago I blogged about the following question of Yaakov Kupitz

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?

Kupitz asked, in particular, if every point set has a line through at least two of its points which is balanced in the sense that the number of points on either side differ by at most some fixed constant c. David Conlon and Jeck Lim showed that if you allow pseudolines rather than lines, the answer is no!

Kupitz’s question extends to pseudolines where it can be formulated using the method of  allowable sequence of permutations introduced by Goodman in Pollack. The best known upper bound C = O(log log n) was proved by Rom Pinchasi and Rom’s proof uses the method of allowable sequence of permutations and applies to pseudolines. Conlon and Lim’s proof shows that for pseudolines, C = Ω(log log n) .

Congratulations David and Jeck!

~~~~~~

Some papers by Lim Jeck on ArXiv