Hostname: page-component-78c5997874-m6dg7 Total loading time: 0 Render date: 2024-11-14T11:14:05.527Z 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: [email protected])
Get access Rights & Permissions [Opens in a new window]

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.

MSC classification

Primary: 52C35: Arrangements of points, flats, hyperplanes
Secondary: 52C10: Erdős problems and related topics of discrete geometry
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 26 , Issue 5 , September 2017 , pp. 720 - 745
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 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