The square-root growth conjecture for distinct distance subsets

At least 13 years old · documented by

Let PP be a set of NN points in the plane, and let δ(N)\delta(N) denote the largest size of a subset of PP whose pairwise distances are all distinct. For every ϵ>0\epsilon>0, consider a constant cϵ>0c_\epsilon>0 independent of NN. Distinct distance subset conjecture. For every ϵ>0\epsilon>0, there exists some constant cϵ>0c_\epsilon>0 such that

δ(N)≥cϵN1/2−ϵ.\delta(N)\ge c_\epsilon N^{1/2-\epsilon}.

The preceding argument gives a lower bound of order N1/3/log⁡NN^{1/3}/\log N, while the conjectured bound is close to the square-root upper bound established earlier in the paper. The source presents this as an inclination to conjecture, so its resolution is not supplied here.

References

Primary source

Marcos Charalambides, “A note on distinct distance subsets”, arXiv:1211.1776 (2012).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.