General Position Subsets and Independent Hyperplanes in d-Space

الأصل · EN

Erdős asked what is the maximum number α(n) such that every set of n points in the plane with no four on a line contains α(n) points in general position. We consider variants of this question for d-dimensional point sets and generalize previously known bounds. In particular, we prove the following two results for fixed d: - Every set H of n hyperplanes in Rᵈ contains a subset S H of size at least c (n n)¹/ᵈ, for some constant c=c(d)>0, such that no cell of the arrangement of H is bounded by hyperplanes of S only. - Every set of cqᵈ q points in Rᵈ, for some constant c=c(d)>0, contains a subset of q cohyperplanar points or q points in general position. Two-dimensional versions of the above results were respectively proved by Ackerman et al. [Electronic J. Combinatorics, 2014] and by Payne and Wood [SIAM J. Discrete Math., 2013].