[2604.05607] 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 $\alpha_s(H_r(n))$, showing that \[ \alpha_s\left(H_r(n)\right)=\Theta\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.

View PDF HTML (experimental) 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 $\alpha_s(H_r(n))$, showing that \[ \alpha_s\left(H_r(n)\right)=\Theta\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…

saved by

• Luke Hawranick

related reading

• Induced rational exponents near twoarxiv.org
• [2603.23431] On the number of families avoiding a subposetarxiv.org
• Exact Stability for Turan's Theoremarxiv.org
• parity edge coloringmilans.us
• Random Turán Problems for Graphs with a Vertex Complete to One Partarxiv.org
• [2604.27639] How large part of a graph can be covered by the neighborhoods of k vertices?arxiv.org
• nullstellensatzweb.math.princeton.edu
• [2305.02725] Two-round Ramsey games on random graphsarxiv.org
• [2604.06521] The Exact Saturation Number for the Diamondarxiv.org
• [2604.04115] Gallai 3-colourings of random graphsarxiv.org
• Arborescences of Random Covering Graphsarxiv.org
• Helly Theorems for Generalized Turán Problemsarxiv.org