Hostname: page-component-74656f9884-j7cmm Total loading time: 0 Render date: 2026-11-07T04:26:58.664Z Has data issue: false hasContentIssue false
  • English
  • Français

Sets in Almost General Position

Part of: Discrete geometry

Published online by Cambridge University Press:  18 April 2017

LUKA MILIĆEVIĆ
LUKA MILIĆEVIĆ*
Affiliation:
Department of Pure Mathematics and Mathematical Statistics, Wilberforce Road, Cambridge CB3 0WB, UK (e-mail: lm497@cam.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

MSC classification

Primary: 52C35: Arrangements of points, flats, hyperplanes
Secondary: 52C10: Erdős problems and related topics of discrete geometry

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 5 , September 2017 , pp. 720 - 745
Copyright
Copyright © Cambridge University Press 2017 

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 33–43.CrossRefGoogle Scholar
[2] Erdős, P. (1986) On some metric and combinatorial geometric problems. Discrete Math. 60 147–153.Google Scholar
[3] Füredi, Z. (1991) Maximal independent subsets in Steiner systems and in planar sets. SIAM J. Discrete Math. 4 196–199.Google Scholar
[4] Furstenberg, H. and Katznelson, Y. (1991) A density version of the Hales–Jewett theorem. J. d'Analyse Mathématique 57 64–119.Google Scholar
[5] Polymath, D. H. J. (2012) A new proof of the density Hales–Jewett theorem. Ann. of Math. 175 1283–1327.Google Scholar