Skip to main content
2 of 2
capitalized Hamming (else it looks pork-related); like +-> as
David Handelman
  • 4.7k
  • 2
  • 23
  • 35

Union of Hamming balls

Let $V \subseteq \{0,1\}^n$, $\log|V| = k$. Consider

$V_r:= \bigcup_{x \in V} V_r(x)$, where $V_r(x)$ is a Hamming full-ball of radius $r$ and center $x$.

What is a lower bound for the cardinality of $V_r$? Is the cardinality of $V_r$ the smallest when $V$ is a Hamming full-ball (as in Harper's theorem)?