The ACO Seminar (2019–2020)

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

Before the talk, at 3:10pm, there will be tea and cookies in Wean 6220.