Almost-equidistant sets (Q2175803)

\textit{D. G. Larman} and \textit{C. A. Rogers} [Mathematika 19, 1--24 (1972; Zbl 0246.05020)] introduced the concept of \((M,D,\delta)\)-critical configurations in \(\mathbb{R}^n\): \(M\) points, such that among any \(D+1\) of these points the distance \(\delta\) occurs between two points. This concept is crucial as lower bounds for the chromatic number of the unit distance graph in \(\mathbb{R}^n\) are based on finding \((M,D,1)\)-critical configurations in \(\mathbb{R}^n\) with a large \(M/D\) ratio. The paper under review investigates how big \(M\) can be in an \((M,3,1)\)-critical configuration in \(\mathbb{R}^n\) and proves an upper bound of \(O(n^{3/2})\). (This result has been improved further to \(O(n^{4/3})\), building on ideas of the paper under review, by \textit{A. Kupavskii} et al. [Comb. Probab. Comput. 28, No. 2, 280--286 (2019; Zbl 1435.52008)].) A number of results are given about the maximum \(M\) in low dimension. It is shown that \(M\geq 2n+4\) and it is conjectured that \(M=O(n)\). Note that \((M,3,1)\)-critical configurations have been renamed to almost equidistant sets and the paper uses this new terminology. The paper introduces a more general extremal problem: for positive integers \(d\), \(k\), and \(\ell\) with \(\ell\leq k\), what is the maximum size of a point set \(P\) in \(\mathbb{R}^d\) such that among any \(k+1\) points from \(P\), there are at least \(\ell +1\) points that are pairwise at unit distance. (A similar problem studied previously, with orthogonality instead of unit distance, is also discussed.)