Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-28T05:30:31.346Z Has data issue: false hasContentIssue false

Sets in Almost General Position

Published online by Cambridge University Press:  18 April 2017

LUKA MILIĆEVIĆ*
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: [email protected])

Abstract

Erdős asked the following question: given n points in the plane in almost general position (no four collinear), how large a set can we guarantee to find that is in general position (no three collinear)? Füredi constructed a set of n points in almost general position with no more than o(n) points in general position. Cardinal, Tóth and Wood extended this result to ℝ3, finding sets of n points with no five in a plane whose subsets with no four points in a plane have size o(n), and asked the question for higher dimensions: for given n, is it still true that the largest subset in general position we can guarantee to find has size o(n)? We answer their question for all d and derive improved bounds for certain dimensions.

Type
Paper
Copyright
Copyright © Cambridge University Press 2017 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Cardinal, J., Tóth, C. and Wood, D. R. (2017) General position subsets and independent hyperplanes in d-space. Journal of Geometry 108 3343.CrossRefGoogle Scholar
[2] Erdős, P. (1986) On some metric and combinatorial geometric problems. Discrete Math. 60 147153.Google Scholar
[3] Füredi, Z. (1991) Maximal independent subsets in Steiner systems and in planar sets. SIAM J. Discrete Math. 4 196199.Google Scholar
[4] Furstenberg, H. and Katznelson, Y. (1991) A density version of the Hales–Jewett theorem. J. d'Analyse Mathématique 57 64119.Google Scholar
[5] Polymath, D. H. J. (2012) A new proof of the density Hales–Jewett theorem. Ann. of Math. 175 12831327.Google Scholar