Mozhgan Mirzaei, University of California, San Diego

Abstract

The famous Szemerédi-Trotter theorem states that any arrangement of n points and n lines in the plane determines O(n 4/3) incidences, and this bound is tight. Although there are several proofs for the Szemerédi-Trotter theorem, our knowledge of the structure of the point-line arrangements maximizing the number of incidences is severely lacking. In this talk, we present some Turán-type results for point-line incidences. Let L1 and L2 be two sets of t lines in the plane and let P = {`1 ∩ `2 : `1 ∈ L1, `2 ∈ L2} be the set of intersection points between L1and L2. We say that (P,L1 ∪ L2) forms a natural t × t grid if |P| = t 2, and conv(P) does not contain the intersection point of some two lines in Li, for i = 1, 2. For fixed t > 1, we show that any arrangement of n points and n lines in the plane that does not contain a natural t × t grid determines O(n 43 −ε) incidences, where ε = ε(t). We also provide a construction of n points and n lines in the plane that does not contain a natural 2 × 2 grid and determines at least Ω(n1+ 114 ) incidences.

This is joint work with Andrew Suk