Large Complete Bipartite Subgraphs In Incidence Graphs Of Points And Hyperplanes
Roel Apfelbaum, Micha Sharir · SIAM Journal on Discrete Mathematics · 2007
We show that if the number I of incidences between m points and n planes in $\mathbb{R}^3$ is sufficiently large, then the incidence graph (which connects points to their incident planes) contains a large complete bipartite subgraph involving r points and s planes, so that $rs \ge \frac{I^2}{mn} - a(m+n)$, for some constant $a>0$. This is shown to be almost tight in the worst case because there are examples of arbitrarily large sets of points and planes where the largest complete bipartite incidence subgraph records only $\frac{I^2}{mn}-\frac{m+n}{16}$ incidences. We also take some steps towards generalizing this result to higher dimensions.