Extermal Combinatorics II: Some Geometry and Number Theory

By Gil Kalai

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.

The solution to problem IV is given by:

The Trotter Szemeredi Theorem: The number I of incidence between t points and s lines in the plane is at most $K \max (t,s,t^{2/3}s^{2/3})$ .

In particular the number of incidences of n points and n lines in the plane is $O(n^{4/3})$ . This is an Euclidean phenomenon which does not follow from the very basic axioms of geometry about incidences of points and lines: Recall that for a finite projective plane with n lines and n points the number of incidences behaves like $n^{3/2}$ .

Elekes: Bounds for product sums via Trotter-Szemeredi

This is an example of an ingenious, simple, and surprising connection between two areas.

Here is how it goes: Let $A$ be a set of n positive real numbers. Consider the planar set $Z= (A+A) \times (A \cdot A)$ . The number $t$ of points in this set is the quantity we would like to estimate. Now, consider the set of lines of the form $y=(x-a_1) \cdot a_2$ , where $a_1,a_2 \in A$ . Our set of lines contains $s$ lines, $s=n^2$ . Note that for every line of the form $y=(x-a_1) \cdot a_2$ and every $a_3 \in A$ if we let $x=a_1 +a_3$ we get $y=a_3 \cdot a_2$ . Thus the point $(a_1+a_3,a_2\cdot a_3) \in Z$ is on the line. We have identified $n$ points of Z on every line in our family of lines. In sum, the number of incidence is at least $n^3$ .

Aha! But now we can apply Trotter Szemeredi’s theorem: $n^3 \le K \max (t, n^2, t^{2/3} n^{4/3})$ . This gives $t^{2/3} \ge K' n^{3-4/3}$ so $t \ge n^{5/2}$ .

In order to prove the Trotter-Szemeredi theorem we will need the following:

The Crossing Theorem: A graph drawn in the plane with v vertices and e edges, e>5v has at least $1/70 e^3/v^2$ crossings.

Szekély: Bounds on Incidences via the crossing lemma

This is an example of a surprising ingenious and simple connection in the same area.

Here is how it goes: We can assume that every line is incident to a point. Consider the following graph drawn in the plane. The vertices are the points in our family. The edges correspond to line segments between two consecutive vertices on the same line. Now, this graph has $t$ vertices and $I-s$ edges. (A line incident to k points contributes k-1 edges.) The number of crossings is at most $s \choose 2$ because every crossing represents an intersection point between a pair of lines. Therefore either $I-s \le 5t$ or $t^2 \le 1/70 (I-s)^3/t^2$ .

The bootstrap proof of the crossing lemma

This is an example of a simple new proof that sheds a light on a theorem, yet is it really different from the old proof? (There was an interesting discussion over Gowers’ blog on when two proofs are essentially the same. In this case, I regard the proofs as different while Janos Pach who understand this subject more deeply regards them as the same.)

We start with Euler’s theorem. It implies that a planar graph with v vertices has at most 3v-6 edges. Therefore for a graph G with e edges and v vertices drawn in the plane consider a maximal planar subgraph H and note that every edge not in H crosses an edge in H. So $c \ge e-3v+6$ .

And now we improve this inequality using itself as follows: Start with a graph G with v vertices and e edges, e>5v. Choose at random every vertex with probability p. The resulting random graph H will have v’ verices, e’ edges, and c’ cossings where the expectation of v’ is pv, the expectation of e’ is $p^2e$ the expectation of c’ is $p^4 c$ . It follows that $p^4 c \ge p^2 e - 3 p n$ so we can optimize the value of p and this leads to the crossing lemma.

Problem III about the number of pairs of points at distance one among n points is the plane is a very famous problem (of Erdös, of course) in discrete geometry. Consider a configuration of n points in the plave and the configuration of unit circles around them. The number of pairs of distance one is half the number of points-circles incidences. Trotter and Szemeredi proved an upper bound $K n^{4/3}$ and Szekely’s argument gives a simple proof of this result as well. It is conjectured that the exponent 4/3 can be pushed down to $1+\epsilon$ , for every $\epsilon$ . The Trotter-Szemeredi theorem itself is sharp – there are examples with matching lower bounds. (Up to the multiplicative constant K.)

High dimensions

Conjecture: Let K be a 2-dimensional simplicial complex with e edges and t triangles. Then for every embedding of K into $R^4$ the number of crossing is at least $C t^4/e^3$ .

As pointed out by Dey and Pach, this conjecture would follow (using the probabilistic argument above) from the following:

Conjecture (Sarkaria): Let K be a 2-dimensional simplicial complex with $f_2(K) \ge 4 f_1(K)$ then K cannot be embedded to $R^4$ . (Anna Gundert pointed out that the stong version I suggested where we assume only $f_2(K) \ge 4 f_1(K)-10 f_0(K) +20$ is easily seen to be false.)

(There are similar conjectures for higher dimensions.)

Sarkaria’s conjecture is closely related to the “g-conjecture” that I plan to devote a special post to.

Problem: What is the maximum number of incidences between s lines and t planes in $R^4$ ?

Unlike the planar case I do not know of a relation between the incidence problem and the crossing problem in high dimensions.

Tags: Additive combinatorics, Extremal combinatorics, Geometric combinatorics

This entry was posted on July 17, 2008 at 10:22 pm and is filed under Combinatorics, Open problems. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

One Response to “Extermal Combinatorics II: Some Geometry and Number Theory”

Plans and Updates « Combinatorics and more Says:
August 14, 2008 at 10:22 am
[...] combinatorics. Part I was an introduction to the subject and dealt with extremal set theory. Part II was about simple extremal problems in plane geometry and additive number theory, and about difficult [...]

Combinatorics and more