MAT 584: Incidence Theorems and Their Applications
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.
[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.
II. Szemeredi-Trotter in finite fields.
III. Kakeya sets.
IV. Sylvester-Gallai type theorems.
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.