On the diameter of separated point sets with many nearly equal distances (Q850083)

Consider a finite separated set \(S\) of \(n\) points in \(d\)-dimensional Euclidean space \({\mathbb R}^d\), i.e., the minimum distance between two points in \(S\) is at least \(1\). Erdős conjectured that for any \(\gamma>0\), if \(S\) is a separated set of \(n\) points in \({\mathbb R}^3\) such that for some \(t>0\), the distances determined by at least \(\gamma n^2\) pairs of points in \(S\) are all in the interval \([t,t+1]\), then the diameter of \(S\) is at least \(c(\gamma)n\) for some \(c(\gamma)>0\). This was proved by the authors in an earlier paper [Comput.\ Geom.\ 34, 11--19 (2006; Zbl 1096.52009)]. Here the following generalization is shown: For any \(\gamma>0\), if \(S\) is a separated set of \(n\) points in \({\mathbb R}^d\) such that for some \(t>0\), the distances determined by at least \(\gamma n^2\) pairs of points in \(S\) are all in the interval \([t,t+1]\), then the diameter of \(S\) is at least \(c(\gamma, d)n^{2/(d-1)}\) for some \(c(\gamma,d)>0\). The upper bound is asymptotically sharp for all \(d\geq 3\). The proof makes use of Szemerédi's regularity lemma and a geometric Ramsey-theoretic result of \textit{N. Alon} et al.\ [J. Comb. Theory, Ser. A 111, 310--326 (2005; Zbl 1099.14048)].