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 C \le n/3, Alon proved that C \le K\sqrt n, Perles showed that C \le K\log n, and Rom Pinchasi showed that C \le K\log \log n. This is the best known upper bound.  (K 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 n/2-K\log \log n 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. Continue reading

Extermal Combinatorics II: Some Geometry and Number Theory

Extremal problems in additive number theory

Our first lecture dealt with extremal problems for families of sets. In this lecture we will consider extremal problems for sets of real numbers, and for geometric configurations in planar Euclidean geometry. 

Problem I: Given a set A of n real numbers, how small can the set A+A={a+a': a,a’ \in A} be?

If A={1,2,…,n} |A+A|=2n-1. Suppose the elements of A are a_1,a_2, \dots, a_n and a_1< a_2<a_3\dots a_n. Note that a_1+a_1<a_1+a_2<a_1+a_2< \dots  a_1+a_n<a_2+a_n<\dots a_n+a_n. So we identified 2n-1 distinct elements in A+A. This is the Cauchy-Davenport theorem.  

Problem II: Given a set A of n positive real numbers, how small can be the set A \cdot A={a\cdot a': a,a’ \in A}?

You may protest (again, like in the first lecture,) that I regard problem II a different problem. You can move from problem II to problem I by taking the logarithm of all elements in A, or you can simply use the same proof with the sum replaced by a product. The proof relies only on very basic monotonicity properties of these operations.

OK, lets have another problem II.

Problem II: Given a set A of n real numbers, how small can the quantity max (|A+A|, |A \cdot A|) be? 

This problem was asked by Erdös, and in hindsight it is a very good problem. Erdös conjectured that the maximum behaves like n^2, and this is open.  We will see below a wonderful proof by Elekes that the maximum is (up to a multiplicative constant) at least n^{5/4}. The exponent 5/4 was improved twice(!!) by Jozsef Solymosi and there is a very nice post about his most recent ingenious proof for a lower bound max (|A+A|, |A \cdot A|) \ge (1/2) n^{4/3} (\log n)^{-1/3} in Izabella Laba’s blog. 

(Update 2/1/2008: “product-sum theorems” of this type grew into a large area with surprising applications in math and CS. They give a strong tool to extract randomness, and they are useful when we consider product of matrices where sums and products are naturally entangled. Here is a recent relevant post written by Herald Helfgott from Izabella Laba’s blog.)

Extremal problems in plane geometry

Problem III:  Given n points in the plane what is the maximum number of pairs among them at distance ‘1’

Problem IV:  Given s points and t lines in the plane what is the maximum number of incidences between them.

An incidence is a pair (p,\ell ) where p  is a point \ell  is a line and p \in \ell.

Problem V: Given a graph G with v vertices and e edges what is the minimum number of crossings in a planar drawing of G.

The second of my extremal combinatorics lectures was devoted to the surprising connections that were found between the above problems. There is also a very nice post about this material on Terry Tao’s blog. To show you something new I will describe a few problems in higher dimensions at the end.

Continue reading