### Approximate Euclidean Ramsey theorems

#### Abstract

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 R^{d}contains an arbitrary large approximate grid, if*L*is large enough. A further generalization for any finite pattern in R^{d}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 R^{d}contains an arbitrarily large subset of almost collinear points. No separation condition is needed in this case.#### Full Text:

PDFDOI: http://dx.doi.org/10.20382/jocg.v2i1a2

ISSN: 1920-180X