Additive Combinatorics and Incidence Geometry: The Szemeredi-Trotter Theorem

Additive Combinatorics is new discipline in mathematics with connections to additive number theory, fourier analysis, graph theory and probability. The field has numerous applications to various other fields, including Incidence Geometry (which focuses on the properties of lines and points in various geometries in a combinatorial sense). We consider the survey of Additive Combinatorics and its applications to Incidence Geometry by Zeev Dvir [1], and present in particular the Szemeredi-Trotter problem from [1]. The Szemeredi-Trotter theorem basically asks that given a set of points and a set of lines, what is the maximum number of incidences that can exist between the lines and the points? We consider the cases of finite fields and reals and examine the upper bounds on the number of incidences in both settings. This project was done in conjuction with Anurag Sahay, a fourth year undergraduate in the Dept. of Computer Science and Engineering, who read on the Kakeya Problem, which deals with the notion of “size” of a subset of Rn or of Fn which has a “line” in every “direction”. at the same time as when I was reading on the Szemeredi-Trotter Theorem, and both of us attended each others project presentations. The presentations were also attended by Dr. Nitin Saxena and Dr. Rajat Mitta