# On a semilinear Zarankiewicz problem

## Speaker:

## Institution:

## Time:

Given a set $P$ of $n$ points on the $xy$-plane and a set $R$ of $n$ solid rectangles with edges parallel to the axes, and assuming that no two points in $P$ lie in two rectangles in $R$, what is the maximum size of the set $I = \{ (p, r) \in P \times R : p \in r\}$ of incidences between $P$ and $R$? For the related problem where $R$ is replaced by a set $L$ of $n$ lines in the planes, the Szemerédi–Trotter Theorem gives us an upper bound $Cn^{4/3}$ for the size of the set of incidences between $P$ and $L$ where $C$ is a constant (independent of n). Moreover, there are examples showing that the exponent $4/3$ is optimal here. A result by Jacob Fox, Janos Pach, Adam Sheffer, and Andrew Suk yields the corresponding upper bound $|I| < Cn^{12/7+ 1/10000}$ with $C$ a constant. However, using an idea from logic (namely, induction on the complexity of formulas), we can significantly improve this bound to

$$ |I| < Cn (\ln n)^3 \quad \text{ with } C \text{ a constant}. $$

We also provide for every fixed constant $C$ and arbitrarily large $n$ an example where $ |I| > C n (\ln n)^{1/2} $. The difference between the point-rectangle incidence problem and the point-line incidence problem hints at the modular/ non-modular dividing line in model theory: the incidence relation in the former case is semilinear (i.e., definable in the real ordered additive group), while the incidence in the latter case is semialgebraic (i.e., definable in the real ordered field) but not semilinear. (Joint with Abdul Basit, Artem Chernikov, Sergei Starchenko, and Terence Tao)