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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.