A bichromatic incidence bound and an application (Q650111)

Given \(n\) points in the Euclidean \(d\)-space, of which \(k\) are colored red, there are \(O_d(m^{2/3}k^{2/3}n^{(d-2)/3}+kn^{d-2}+m)\) incidences between red points and the \(m\) hyperplanes spanned by all \(n\) points provided that \(m=\Omega(n^{d-2})\). This bound is tight. For the case ``all points red'', i.e., \(n=k\), this was proved by \textit{P. K. Agarwal} and \textit{B. Aronov} [Discrete Comput. Geom. 7, No.4, 359--369 (1992; Zbl 0747.68092)]. The paper uses this new bound to prove a Beck-Erdős type theorem in 3-space: given \(n\) points, such that no more than \(n-k\) of them lie on any plane or on any two lines, this set spans \(\Omega(nk^2)\) lines. A well-known conjecture of Purdy asserted that, for \(n\) sufficiently large, if a set of \(n\) points in the \(d\)-dimensional space cannot be covered by a set of flats whose ranks sum to \(d+1\), then the set of \(n\) points spans at least as many hyperplanes as \((d-2)\)-flats (the rank of a flat is one more than its dimension). \textit{B. Grünbaum} and \textit{G. C. Shephard} [Coxeter Festschrift IV, Mitt. Math. Semin. Giessen 166, 49--101 (1984; Zbl 0558.51001)] gave counterexamples for this conjecture in 3-space up to \(n=16\). The paper under review produces infinitely many counterexamples in any dimension at least 4 and presents a corrected conjecture.