A note on the largest bipartite subgraph in point-hyperplane incidence graphs

Abstract

Given $m$ points and $n$ hyperplanes in ${\mathbb{R}}^d$, 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 only match in three dimensions. In this paper we close the gap in four and five dimensions, up to some logarithmic factors.

6 pages