Exponential packing of a Hamming cube
= Exponential packing of a Hamming cube
{title2=$|S|\geq e^{9n/32},\quad d_H(s,s^{\prime})\geq n/8$}
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$.