A bichromatic incidence bound and an application

DOI10.1007/S00454-011-9367-3MaRDI QIDQ650111zbMATH OpenOpenAlexFDO

Authors Ben Lund, George B. Purdy, Justin W. Smith

Publication date 25 November 2011

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1006.3878

Beck-Erdős type theorem conjecture of Purdy hyperplane arrangement incidence bound

Erd?s problems and related topics of discrete geometry (52C10) Arrangements of points, flats, hyperplanes (aspects of discrete geometry) (52C35)

Abstract: We prove a new, tight upper bound on the number of incidences between points and hyperplanes in Euclidean d-space. Given n points, 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 the k red points and m hyperplanes spanned by all n points provided that m = Omega(n^{d-2}). For the monochromatic case k = n, this was proved by Agarwal and Aronov. We use this incidence bound to prove that a set of n points, no more than n-k of which lie on any plane or two lines, spans Omega(nk^2) planes. We also provide an infinite family of counterexamples to a conjecture of Purdy's on the number of hyperplanes spanned by a set of points in dimensions higher than 3, and present new conjectures not subject to the counterexample.

Review text

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.

Recommendations

Cites work

Cited in

(9)

This page was built for publication: A bichromatic incidence bound and an application

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q650111)