Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2604.05607 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866911571939164160 |
|---|---|
| author | Balogh, József Chen, Ce Li, Bowen |
| author_facet | Balogh, József Chen, Ce Li, Bowen |
| contents | 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 $α_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2604_05607 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Forbidding Exactly One Hamming Distance Balogh, József Chen, Ce Li, Bowen Combinatorics Primary: 05D05, Secondary: 05D40, 94B65, 05C35 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 $α_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. |
| title | Forbidding Exactly One Hamming Distance |
| topic | Combinatorics Primary: 05D05, Secondary: 05D40, 94B65, 05C35 |
| url | https://arxiv.org/abs/2604.05607 |