2026-07-22T11:38:47Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:17909 2024-03-12T12:01:16Z ddc:004 open_access

On Higher Dimensional Point Sets in General Position Suk, Andrew Zeng, Ji independent sets hypergraph container method generalised Sidon sets A finite point set in ℝ^d is in general position if no d + 1 points lie on a common hyperplane. Let α_d(N) be the largest integer such that any set of N points in ℝ^d with no d + 2 members on a common hyperplane, contains a subset of size α_d(N) in general position. Using the method of hypergraph containers, Balogh and Solymosi showed that α₂(N) < N^{5/6 + o(1)}. In this paper, we also use the container method to obtain new upper bounds for α_d(N) when d ≥ 3. More precisely, we show that if d is odd, then α_d(N) < N^{1/2 + 1/(2d) + o(1)}, and if d is even, we have α_d(N) < N^{1/2 + 1/(d-1) + o(1)}. We also study the classical problem of determining the maximum number a(d,k,n) of points selected from the grid [n]^d such that no k + 2 members lie on a k-flat. For fixed d and k, we show that a(d,k,n)≤ O(n^{d/{2⌊(k+2)/4⌋}(1- 1/{2⌊(k+2)/4⌋d+1})}), which improves the previously best known bound of O(n^{d/⌊(k + 2)/2⌋}) due to Lefmann when k+2 is congruent to 0 or 1 mod 4. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Andrew Suk and Ji Zeng 2023 Is Part Of LIPIcs, Volume 258, 39th International Symposium on Computational Geometry (SoCG 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2023.59 urn:nbn:de:0030-drops-179097 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2023.59 eng https://creativecommons.org/licenses/by/4.0/legalcode