Suppose that $A$ is a large subset of $n$-dimensional Hamming cube ,$|A| \geq 2^{\beta n}$, and we know that the pairwise distance between the points in $A$ is at least $\alpha n$ for some $0< \alpha < 1$. what can be stated about the diameter of $A$? clearly ,

$\alpha n\leq d(A) \leq n$.

But is there any idea to obtain better bounds?

For example, can I prove that there is a configuration of $2^{\beta n}$ points with that distance condition and diameter less than $4 \alpha n$?

Thank you very much.

  • $\begingroup$ It seems like it can be $n$ at least for some choice of $\alpha$ and $\beta$. You can take some good code on a sphere. The add $0^n$ and $1^n$. You will still have a linear distance and an exponential number of points, but the diameter is now $n$. $\endgroup$ – ivmihajlin Nov 21 '17 at 7:38
  • $\begingroup$ @ivmihajlin I surmise that the OP wants to minimize the diameter for given $\alpha$ and $\beta$ asymptotically when $n$ is large, not to maximize it though it is not clear to me how to move the balls apart in an easy way. $\endgroup$ – fedja Nov 21 '17 at 17:59
  • $\begingroup$ If we want to minimize the diameter - we can just take some code on the subcube. $\endgroup$ – ivmihajlin Nov 22 '17 at 11:41

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.