Nearly k-distance sets

2019/06/06 by Frankl, Nóra, Kupavskii, Andrey
#Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.1906.02574

Abstract

We say that a set of points S⊂ ℝ^d is an ε-nearly k-distance set if there exist 1≤ t₁≤ …≤ t_k, such that the distance between any two distinct points in S falls into [t₁,t₁+ε]∪…∪[t_k,t_k+ε]. In this paper, we study the quantity M_k(d) = lim_{ε→ 0}max\|S| : S is an ε-nearly k -distance set in ℝ^d\ and its relation to the classical quantity m_k(d): the size of the largest k-distance set in ℝ^d. We obtain that M_k(d) = m_k(d) for k=2,3, as well as for any fixed k, provided that d is sufficiently large. The last result answers a question, proposed by Erdős, Makai and Pach. We also address a closely related Turán-type problem, studied by Erdős, Makai, Pach, and Spencer in the 80's: given n points in ℝ^d, how many pairs of them form a distance that belongs to [t₁,t₁+1]∪…∪[t_k,t_k+1], where t₁,…, t_k are fixed and any two points in the set are at distance at least 1 apart? We establish the connection between this quantity and a quantity closely related to M_k(d-1), as well as obtain an exact answer for the same ranges k,d as above.

Related

• Two nearly equal distances in R^d
• Nearly equal distances in the plane, II
• Constructions of maximum few-distance sets in Euclidean spaces
• On a generalization of distance sets
• A problem of Erdős about rich distances