Almost-equidistant sets

DOI10.1007/S00373-020-02149-WzbMATH Open1439.52016arXiv1706.06375OpenAlexW3007385743MaRDI QIDQ2175803FDOQ2175803

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)

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})$.

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

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

zbMATH Keywords

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (9)

• Approximate inverse limits and (m,n)-dimensions
• Bounding the Size of an Almost-Equidistant Set in Euclidean Space
• Quasiextremal distance sets
• Nearly \(k\)-distance sets
• Almost equidistant points on \(S^{D-1}\)
• Matching random colored points with rectangles
• Equidistant Sets in Plane Triodic Continua
• Almost-equidistant sets
• Title not available (Why is that?)

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)