Suppose $X \subseteq \lbrace 0 , 1 \rbrace ^{m}$ such that $|X| \geq 2^{0.8m}$, and $m \geq 2$, then prove that there exists $x,y \in X$ with $||x - y||\_{1} \geq m/2$. 


My approach to prove this was if there is no such $x,y$, then $X$ is inside a Hamming ball of radius $m/2$ . But this does not give me a tight enough inequality on the size of $X$. 



Isoperimetric inequality on the Hamming cube
The problem of obtaining the largest set $X$ under the condition that its largest pairwise distance is bounded from above is known as the anticode problem, since it is naturally dual to the problem of finding an optimal error correcting code, where the smallest pairwise distance is bounded from below. It is apparently a theorem of Kleitman (<http://dx.doi.org/10.1016/S0021-9800(66)80027-3>) that the best binary anticode of diameter $2k$ and length $m$ is simply constructed by taking all strings of length $m$ with at most $k$ 1s (that is, a Hamming ball of radius $k$). If you let $k=\lfloor(\lceil m/2\rceil-1)/2\rfloor$ (I hope I got this right now), then you will find that the size of this anticode exceeds the bound you give in your question, and so the statement you cited is false, as already noted by Robert and Christian. It can be corrected by increasing $0.8$ to a slightly higher number, as they note.


Some more on Hamming anticodes: <http://dx.doi.org/10.1006/aama.1998.0588>


