Almost-equidistant sets

DOI10.1007/S00373-020-02149-WMaRDI QIDQ2175803zbMATH OpenOpenAlexFDO

Authors Martin Balko, Attila Pór, Manfred Scheucher, Konrad J. Swanepoel, Pavel Valtr

Publication date 30 April 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1706.06375

zbMATH Keywords

\((M,D,\delta)\)-critical configurationalmost equidistant setpoint configuration

Mathematics Subject Classification ID

Ramsey theory (05D10) Erd?s problems and related topics of discrete geometry (52C10)

Abstract: For a positive integer $d$, a set of points in $d$-dimensional Euclidean space is called almost-equidistant if for any three points from the set, some two are at unit distance. Let $f(d)$ denote the largest size of an almost-equidistant set in $d$-space. It is known that $f(2)=7$, $f(3)=10$, and that the extremal almost-equidistant sets are unique. We give independent, computer-assisted proofs of these statements. It is also known that $f(5)ge16$. We further show that $12leqf(4)leq13$, $f(5)leq20$, $18leqf(6)leq26$, $20leqf(7)leq34$, and $f(9)geqf(8)geq24$. Up to dimension $7$, our work is based on various computer searches, and in dimensions $6$ to $9$, we give constructions based on the known construction for $d=5$. For every dimension $dge3$, we give an example of an almost-equidistant set of $2d+4$ points in the $d$-space and we prove the asymptotic upper bound $f(d)leO(d^{3/2})$.

Review text

\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.)

Recommendations

• Bounding the Size of an Almost-Equidistant Set in Euclidean Space
• scientific article; zbMATH DE number 1234826
• Circle grids and bipartite graphs of distances
• The additive structure of Cartesian products spanning few distinct distances
• The multiplicity of the two smallest distances among points
• Unit distances and diameters in Euclidean spaces
• Characterizing optimal point sets determining one distinct triangle
• Popular distances in 3-space
• A product inequality for extreme distances
• scientific article; zbMATH DE number 2140321

Cites work

• A note on Ramsey numbers
• Almost equidistant points on \(S^{D-1}\)
• Almost-equidistant sets
• Bounding the Size of an Almost-Equidistant Set in Euclidean Space
• Cycles of nonzero elements in low rank matrices
• scientific article; zbMATH DE number 17660 (Why is no real title available?)
• scientific article; zbMATH DE number 2068112 (Why is no real title available?)
• Isomorph-Free Exhaustive Generation
• Large sets of nearly orthogonal vectors
• On almost-equidistant sets
• On the space chromatic number
• Problems and results in extremal combinatorics. I.
• Ramsey numbers \(R(K_3, G)\) for graphs of order 10
• Sets of vectors with many orthogonal pairs
• Small Ramsey numbers
• The generation of maximal triangle-free graphs
• The minimum semidefinite rank of a triangle-free graph
• The Ramsey number R(3, t) has order of magnitude t²/log t
• The realization of distances within sets in Euclidean space

Cited in

(11)

• On almost-equidistant sets
• Almost-equidistant sets
• On almost-equidistant sets. II
• scientific article; zbMATH DE number 33590 (Why is no real title available?)
• Equidistant Sets in Plane Triodic Continua
• Quasiextremal distance sets
• Amiable and almost amiable fixed sets. Extension of the Brouwer fixed point theorem
• Bounding the Size of an Almost-Equidistant Set in Euclidean Space
• Matching random colored points with rectangles
• Almost equidistant points on \(S^{D-1}\)
• Nearly k-distance sets

Describes a project that uses

Uses Software

• OEIS
• Triangleramsey

This page was built for publication: Almost-equidistant sets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2175803)