Triangle-free subsets of the $r$-distance graph of the hypercube

Abstract

Given the $r$-distance graph on the hypercube $\F_2^n$, where two vertices are adjacent if their Hamming distance is exactly $r$, we study the maximum size $T(n,r)$ of a triangle-free set of vertices. For even $r\le n/2$, we prove \[ T(n,r)=O\!\left(\frac{r2^n}{n+1}\right). \] In particular, $T(n,r)=o(2^n)$ whenever $r=o(n)$. For fixed $0<\alpha <2/3$, we also prove that if $r=\alpha n$, where $n$ ranges over integers such that $\alpha n$ is an even integer, then \[ T(n,r)\le 2^{(1-\varepsilon_α)n} \] for some ${\epsilon }_{\alpha }>0$. We also obtain lower bounds in various regimes of $r$ as a function of $n$.

A new co-author was added in the second version. The lower bound has been improved in certain sub-linear regimes. The upper bound in the linear regime has been strengthened to show that every triangle-free set has exponentially small density in the cube, answering a question posed in the second version