2016/01/26 by Luka Milićević, Milićević, Luka
Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #math.CO
paper · pdf · doi:10.48550/arxiv.1601.07206
20 pages, no figures
arxiv created 2016/01/26 · arxiv updated 2016/01/28
Erdős asked the following question: given n points in the plane in almost general position (no 4 collinear), how large a set can we guarantee to find that is in general position (no 3 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 5 on a plane whose subsets with no 4 points on 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.