The largest complete bipartite subgraph in point-hyperplane incidence graphs (Q2288177): Difference between revisions

Summary: 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. \textit{R. Apfelbaum} and \textit{M. Sharir} [SIAM J. Discrete Math. 21, No. 3, 707--725 (2007; Zbl 1141.05040)] 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.