Hamming cube ($\{-1,1{\}}^n$)

The Hamming cube is $\{-1,1{\}}^n$, or equivalently $\{0,1{\}}^n$, equipped with Hamming distance. Under its uniform probability measure, the distance from a fixed vertex has the binomial distribution with parameters $n,1/2$. This converts geometric ball sizes into probability tails.

An inclusion-maximal separated set of separation $an$ covers the Hamming cube by strict-radius $an$ balls. The Hoeffding lower-tail bound for Hamming balls then gives at least $e^{2n(1/2-a{)}^2}$ selected vertices. At $a=1/8$ this yields $e^{9n/32}$ vertices, all separated by at least $n/8$.