Extremal 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.

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.

This entry was posted in Combinatorics, Open problems and tagged , , . Bookmark the permalink.

6 Responses to Extremal Combinatorics II: Some Geometry and Number Theory

  1. Pingback: Plans and Updates « Combinatorics and more

  2. Pingback: Janos Pach: Guth and Katz’s Solution of Erdos’ Distinct Distances Problem | Combinatorics and more

  3. Pingback: Updates and plans III. | Combinatorics and more

  4. Pingback: Basic Notions Seminar is Back! Helly Type Theorems and the Cascade Conjecture | Combinatorics and more

  5. Pingback: Extremal Combinatorics V: POSETS | Combinatorics and more

  6. Pingback: The largest clique in the Paley Graph: unexpected significant progress and surprising connections. | Combinatorics and more

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s