The Largest Complete Bipartite Subgraph in Point-Hyperplane Incidence Graphs

Abstract

Given $m$ points and $n$ hyperplanes in $\mathbb{R}^d$ ($d\geqslant 3)$, if there are many incidences, we expect to find a big cluster $K_{r,s}$ in their incidence graph. Apfelbaum and Sharir found lower and upper bounds for the largest size of $rs$, which match (up to a constant) only in three dimensions. In this paper we close the gap in four and five dimensions, up to some polylogarithmic factors.