= Kleitman diametric theorem
{c}
{title2=$D(n,2q)=\sum_{i=0}^q\binom ni,\quad D(n,2q+1)=2\sum_{i=0}^q\binom{n-1}i$}
A family in the Boolean lattice whose pairwise Hamming distances are at most $d<n$ has size at most $D(n,d)$. Downward compression followed by <elementary set shifts> preserves the distance bound. In the resulting down-set, the section containing the last coordinate has diameter at most $d-2$: two members leave a coordinate free, and shifting the last coordinate to it creates a pair with two additional disagreements. This gives the recurrence $D(n,d)=D(n-1,d)+D(n-1,d-2)$. The boundary case $d=n-1$ follows by pairing complementary sets. Hamming balls attain the even case; the union of two radius-$q$ balls with adjacent centers attains the odd case.
Back to article page
