Nearly equal distances and Szemerédi's regularity lemma (Q2489544)

An aim of this note is the following theorem: Let \(\varepsilon >0\) be fixed and let \(P\) be a separated set of \(n\) points in \(\mathbb{R}^3\) containing at least \(\varepsilon n^2\) pairs \((u,v)\), \(u,v\in P\), with \(\|u-v\|\in[t,t+1]\) for some fixed real number \(t>0\). Then the diameter of \(P\) is at least constant times \(n\) \((\text{diam}(P)=\Omega(n))\). At this a point set is called separated if the minimum distance between two elements is one. This result proves a conjecture by \textit{P. Erdős} [Am. Math. Mon. 53, 248--250 (1946; Zbl 0060.34805)] and \textit{P. Erdős}, \textit{E. Makai} and \textit{J. Pach} [Comb. Probab. Comput. 2, No. 4, 401--408 (1993; Zbl 0798.52017)]. In the proof the Szemerédi's regularity lemma and a Ramsey-type result for dot products of vectors are used.