Hamming ball

In combinatorics, a Hamming ball is a metric ball for Hamming distance. The Hamming ball of radius ${\displaystyle r}$ centered at a string ${\displaystyle x}$ over some alphabet (often the alphabet {0,1}) is the set of all strings of the same length that differ from ${\displaystyle x}$ in at most ${\displaystyle r}$ positions. This may be denoted using the standard notation for metric balls, ${\displaystyle B(s,r)}$. For an alphabet ${\displaystyle X}$ and a string ${\displaystyle x}$, the Hamming ball is a subset of the Hamming space ${\displaystyle X^{|x|}}$ of strings of the same length as ${\displaystyle x}$, and it is a proper subset whenever ${\displaystyle r<|x|}$. The name Hamming ball comes from coding theory, where error correction codes can be defined as having disjoint Hamming balls around their codewords,^[1] and covering codes can be defined as having Hamming balls around the codeword whose union is the whole Hamming space.^[2]

Hamming balls centered at the string "cab" with radius 1 (orange vertices and center), 2 (previous ball plus yellow vertices) and 3 (previous plus gray vertices).

Some local search algorithms for SAT solvers such as WalkSAT operate by using random guessing or covering codes to find a Hamming ball that contains a desired solution, and then searching within this Hamming ball to find the solution.^[2]

A version of Helly's theorem for Hamming balls is known: For Hamming balls of radius ${\displaystyle r}$ (in Hamming spaces of dimension greater than ${\displaystyle r}$), if a family of balls has the property that every subfamily of at most ${\displaystyle 2^{r+1}}$ balls has a common intersection, then the whole family has a common intersection.^[3]