4
$\begingroup$

Let $P$ be a set of $n$ points in the plane and let $D$ be the set of Euclidean distances determined by the pairs of points in $P$. Suppose that for each $d \in D$ there are at most $5$ (unordered) pairs $(A,B) \in P \times P$ so that $AB=d$.

Must $P$ contain a subset of points $P'$ of size $\Omega(n)$ so that the segments with endpoints in $P'$ have all distinct distances?

As stated, it seems like the answer is most likely no. For example, if all points from $P$ lie on the $x$-axis, then there exists a set $A \subset \mathbb{Z}$ with $r_{A}(x) \leq 4$ for each $x \in \mathbb{Z}$ such that no subset $A' \subset A$ of size $|A'| > 2|A|^{2/3}$ is a Sidon set. See for instance Dubickas, Schoen, Silva, Šarka, Finding large co-Sidon subsets in sets with a given additive energy, European Journal of Combinatorics, 34 (2013) 1144-1157.

However, what if we assume that say no line in the plane contains $\Omega(n)$ points from $P$? Can we extract such a subset $P'$? Are there any two-dimensional obstructions?

Improve this question
$\endgroup$
3
  • $\begingroup$ The "no line" condition alone is no good because you can always turn a line interval into an arc of a circle without changing anything. $\endgroup$
    – fedja
    May 17, 2017 at 14:43
  • $\begingroup$ Can you please elaborate? Also, you can assume the points lies on a curve which is not a line (if it makes things easier) $\endgroup$
    – Cosmin Pohoata
    May 20, 2017 at 17:56
  • 1
    $\begingroup$ If you have a bad configuration on an interval, you can take the configuration on a sufficiently large circle with the same arc distances. However the arc distances are equal iff the Euclidean ones are. Thus, you have to rule circles out too. Nothing clever, really, just a stupid observation that you should be careful with how you state the problem. :-) $\endgroup$
    – fedja
    May 20, 2017 at 18:01

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.