MAT 584: Incidence Theorems and Their Applications

Spring 2012

Overview

Incidence theorems describe the way lines, points and other geometric objects intersect each other. Theorems of this sort have found a large number of applications in the past few decades. We will prove some of the seminal results in this area as well as some new and surprising theorems from the past couple of years. We will work both over real/complex space and over finite fields. The course will focus on three general types of problems:

1. Szemeredi-Trotter type problems: How many incidences can a set of lines have with a set of points? The answer to this question is the famous Szemeredi-Trotter theorem. It has various applications to other problems in discrete combinatorics such as the sum-product theorem, counting distances and CS applications (using finite field versions).

2. Kakeya type problems: A Kakeya set is a set in R^n that contains a line segment in each direction. Understanding properties of such sets, such as their dimension, is important in many other areas of mathematics. We will see the most promising approach to this problem using tools from additive combinatorics and prove some of the known bounds. We will also study the finite field version and its applications to CS.

3. Sylvester-Gallai type problems: The classical Sylvester-Gallai theorem states that in every non-collinear set of points there is a line intersecting exactly two points. We will see some far reaching generalizations of this statement and its connections to problems in additive combinatorics, coding theory and computational complexity.

Lecture Notes

[Sep 2012] These notes have been edited into a survey format which can be downloaded here

[Jun 2012] Notes updated.

I. Szemeredi-Trotter type theorems in real space.

• Overview
• Szemeredi-Trotter over the reals
• Applications of Szemeredi-Trotter.
• The Elekes-Sharir Framework.
• The Polynomial Method. The Joints Conjecture.
• The Polynomial Ham-Sandwich Theorem. Polynomial Cell Partitions.
• Proof of the Guth-Katz Incidence Theorem.
• Sum-Product estimates using the Guth-Katz bound.

II. Szemeredi-Trotter in finite fields.

• Ruzsa Calculus.
• Growth in prime fields.
• The Balog-Szemeredi-Gowers Theroem.
• Proof of Szemeredi-Trotter in finite fields.
• Applications to multi-source Extractors.

III. Kakeya sets.

• Kakeya sets over the reals.
• Kakeya sets over finite fields.
• Applications of Kakeya sets to merging random sources.

IV. Sylvester-Gallai type theorems.

• Sylvester-Gallai type theorems in characteristic zero.
• Rank of design matrices.
• Sylvester-Gallai over finite fields.
• Locally Correctable Codes.

Additional Reading

Book chapter by Matousek covering the Szemeredi-Trotter theorem over the reals.

Szekely's paper proving the ST theorem using the crossing number inequality. This paper also contains extensions to incidences of curves and points embedded on a general 2-manifold.'

Elekes's beautiful survey on the sum product theorem over the reals.

An article by Iosevitch discussing connections between Szemeredi-Trotter type theorems, Fourier analysis and convex geometry.

A webpage maintained by Bill Gasarch containing many links on the Erdos distance problem.

Ben Green's Lecture notes on additive combinatorics (includes most of the stuff we will talk about and much more).

Tao's survey article on the Euclidean Kakeya conjecture and its applications in mathematics.

My survey article on the Kakeya problem and its applications in cs.