2
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • $\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, 2017 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, 2017 at 17:59
  • $\begingroup$ If we want to minimize the diameter - we can just take some code on the subcube. $\endgroup$
    – ivmihajlin
    Nov 22, 2017 at 11:41

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.

Browse other questions tagged or ask your own question.