Computer Science/Discrete Mathematics Seminar II

A cornerstone result in geometry is the Szemerédi–Trotter theorem, which gives a sharp bound on the maximum number of incidences between $m$ points and $n$ lines in the real plane. A natural generalization of this is to consider point-hyperplane incidences in higher dimensions. As proposed by Chazelle in the 90's, we are interested in the maximum number of incidences between $m$ points and $n$ hyperplanes, assuming no $s$ points lie in the intersection of $s$ hyperplanes. The latter condition is needed to avoid trivialities, like all hyperplanes intersecting in a line, and all points contained in this line. Starting from dimension 3, matching lower and upper bounds are no longer known for this problem. I will talk about how to prove sharp bounds over arbitrary fields using methods from extremal graph theory, and discuss analogues of this problem concerning point-variety incidences and unit distance graphs.

Based on a joint work with Aleksa Milojević and Benny Sudakov.