2010/04/09 by Adrian Dumitrescu, Dumitrescu, Adrian
Computer Science · Mathematics · #Advanced Graph Theory Research #Advanced Topology and Set Theory #Combinatorics (math.CO) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #FOS: Mathematics #Limits and Structures in Graph Theory #cs.CG #math.CO
paper · pdf · doi:10.48550/arxiv.1004.1654
11 pages, 1 figure.
arxiv created 2010/04/09 · openalex publication_date 2010/04/09 · arxiv updated 2010/04/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
According to a classical result of Szemerédi, every dense subset of 1,2,...,N contains an arbitrary long arithmetic progression, if N is large enough. Its analogue in higher dimensions due to Fürstenberg and Katznelson says that every dense subset of \1,2,...,N\d contains an arbitrary large grid, if N is large enough. Here we generalize these results for separated point sets on the line and respectively in the Euclidean space: (i) every dense separated set of points in some interval [0,L] on the line contains an arbitrary long approximate arithmetic progression, if L is large enough. (ii) every dense separated set of points in the d-dimensional cube [0,L]d in \RRd contains an arbitrary large approximate grid, if L is large enough. A further generalization for any finite pattern in \RRd is also established. The separation condition is shown to be necessary for such results to hold. In the end we show that every sufficiently large point set in \RRd contains an arbitrarily large subset of almost collinear points. No separation condition is needed in this case.