Abstract

We survey recent (and not so recent) results concerning arrangements of lines, points, and other geometric objects and the applications these results have in theoretical computer science and combinatorics. The three main types of problems we will discuss are:

1. Counting incidences: Given a set (or several sets) of geometric objects (lines, points, etc.), what is the maximum number of incidences (or intersections) that can exist between elements in different sets? We will see several results of this type, such as the Szemeredi–Trotter theorem, over the reals and over finite fields and discuss their applications in combinatorics (e.g., in the recent solution of Guth and Katz to Erdos' distance problem) and in computer science (in explicit constructions of multisource extractors).
2. Kakeya type problems: These problems deal with arrangements of lines that point in different directions. The goal is to try and understand to what extent these lines can overlap one another. We will discuss these questions both over the reals and over finite fields and see how they come up in the theory of randomness extractors.
3. Sylvester–Gallai type problems: In this type of problems, one is presented with a configuration of points that contain many 'local' dependencies (e.g., three points on a line) and is asked to derive a bound on the dimension of the span of all points. We will discuss several recent results of this type, over various fields, and see their connection to the theory of locally correctable error-correcting codes.

Throughout the different parts of the survey, two types of techniques will make frequent appearance. One is the polynomial method, which uses polynomial interpolation to impose an algebraic structure on the problem at hand. The other recurrent techniques will come from the area of additive combinatorics.

The author is supported under NSF grant CCF-1217416.

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 exciting applications in the past few decades, both in mathematics and in theoretical computer science. Incidence Theorems and Their Applications presents some of the seminal results in this area as well as recent developments and applications. The presented results fall under three main themes. (i) Counting incidences: How many incidences can a set of lines have with a set of points? This basic question, and its generalizations, plays a role in proving various other theorems, some completely unrelated to geometry. (ii) Kakeya type problems: What is the 'best' way to arrange a set of lines, pointing in different directions, so that their overlap is maximized? Variations of this question appear in problems ranging from analysis and number theory to randomness extractors. (iii) Local to global problems: Suppose that, in a set of points, there are many small subsets that are dependent (for example, three points on a line). Can this information be used to give an upper bound on the dimension of the entire set? Problems of this kind are related to fascinating open problems in locally correctable error correcting codes. Incidence Theorems and Their Applications is aimed at both mathematicians and computer scientists and is suitable as a basis for a one semester course. Ideally, each chapter should be read from start to finish (the different chapters are mostly independent of each other).