Almost Sharp Bounds on the Number of Discrete Chains in the Plane
Nóra Frankl, Andrey Borisovich Kupavskii · COMBINATORICA · 2022
The following generalisation of the Erdős Unit Distance problem was recently suggested by Palsson, Senger, and Sheffer. For a fixed sequence δ = (δ1, …, δk) of k distances, a (k + 1)-tuple (p1, …, pk+1) of distinct points in ℝd is called a k-chain if ∥pj − pj+1∥ = δj for every 1 ≤ j ≤ k. What is the maximum number C (n) of k-chains in a set of n points in ℝd? Improving the results of Palsson, Senger, and Sheffer, we essentially determine this maximum for all k in the planar case. It is only for k ≡ 1 (mod 3) that the answer depends on the maximum number of unit distances in a set of n points. We also obtain almost sharp results for even k in dimension 3, and propose further generalisations.