Point-hyperplane incidences via extremal graph theory

Aleksa Milojević, István Tomon, Benny Sudakov

Published 2024-01-12Version 1

The study of counting point-hyperplane incidences in the $d$-dimensional space was initiated in the 1990's by Chazelle and became one of the central problems in discrete geometry. It has interesting connections to many other topics, such as additive combinatorics and theoretical computer science. Assuming a standard nondegeneracy condition, i.e., that no $s$ points are contained in the intersection of $s$ hyperplanes, the currently best known upper bound on the number of incidences of $n$ points and $m$ hyperplanes in $\mathbb{R}^d$ is $O_{d, s}((mn)^{1-1/(d+1)}+m+n).$ This bound by Apfelbaum and Sharir is based on geometrical space partitioning techniques. In this paper, we propose a novel combinatorial approach to estimate the number of point-hyperplane incidences over arbitrary fields using forbidden induced patterns in incidence graphs. Perhaps surprisingly, this approach matches the best known bounds in $\mathbb{R}^d$ for many interesting values of $m, n, d$, e.g. when $m=n$ and $d$ is odd. Moreover, in finite fields our bounds are sharp as a function of $m$ and $n$ in every dimension. We also study the size of the largest complete bipartite graph in point-hyperplane incidence graphs with a given number of edges and obtain optimal bounds as well.