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.