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
    Commented 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
    Commented 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
    Commented Nov 22, 2017 at 11:41

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .