= Boolean cube expansion from bounded differences
{title2=$|A_t|\geq(1-\varepsilon)2^n$}
For a nonempty $A\subseteq\{0,1\}^n$ of relative size at least $\varepsilon\in(0,1]$, its <Hamming distance> <function> $F(x)=d(x,A)$ has the <bounded differences property> with all constants one. If $\mu=\mathbb EF$, the concentration bound at $F=0$ gives $\varepsilon\leq2e^{-2\mu^2/n}$, so $\mu\leq t/2$ for $t=\sqrt{2n\log(2/\varepsilon)}$. Then $\Pr(F>t)\leq2e^{-2(t-\mu)^2/n}\leq\varepsilon$, proving that the radius-$t$ neighbourhood contains at least $(1-\varepsilon)2^n$ cube points.
Back to article page
