Turán Densities for Small Hypercubes

Abstract

How small can a set of vertices in the $n$-dimensional hypercube $Q_n$ be if it meets every copy of $Q_d$? The asymptotic density of such a set (for $d$ fixed and $n$ large) is denoted by ${\hat{I}}_d^3$. It is easy to see that ${\hat{I}}_d^3\le 1/(d+1)$, and it is known that ${\hat{I}}_d^3=1/(d+1)$ for $d\le 2$, but it was recently shown that ${\hat{I}}_d^3<1/(d+1)$ for $d\ge 8$. In this paper we show that the latter phenomenon also holds for $d=7$ and $d=6$.

8 pages