Forbidding Exactly One Hamming Distance

Abstract

Addressing questions raised in recent papers, we study the $r$-distance graph $H_r(n)$ on the Boolean cube $\{0,1{\}}^n$, where two vertices are adjacent if their Hamming distance is exactly $r$. For fixed integers $s\ge 2$ and even $r\ge 2$, we determine the asymptotic order of the $s$-independence number $\hat{I}{\pm }_s(H_r(n))$, showing that \[ α_s\left(H_r(n)\right)=Θ\left(\frac{2^n}{n^{r/2}}\right). \] The upper bound is derived via a reduction to extremal problems for sunflower-free set systems, while the lower bound is obtained using algebraic constructions based on BCH codes and constant-weight codes.

10 pages