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 $L_1$ and $L_2$ be two sets of $t$ lines in the plane and let $P = \{\ell_1 \cap \ell_2 : \ell_1 \in L_1, \ell_2 \in L_2\}$ be the set of intersection points between $L_1$ and $L_2$. We say that $(P,L_1 \cup L_2)$ forms a natural $t \times t$ grid if $\lvert P\rvert=t^2$, and $\mathop{\text{conv}}(P)$ does not contain the intersection point of some two lines in $L_i$, 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\times t$ grid determines $O(n^{4/3−\varepsilon})$ incidences. We also provide a construction of $n$ points and $n$ lines in the plane that does not contain a natural $2\times2$ grid and determines at least $\Omega(n^{1+1/14})$ incidences.
This is joint work with Andrew Suk.