Packing vertices on a hypercube graph? Imagine a graph where the vertices and edges model an n dimensional hypercube (a line, a square, a cube and so on). A red vertex must have a minimum distance of 3 from every other red vertex. The problem is to maximise the number of red vertices for a given n.
I have absolutely no idea where to start. Any help is appreciated.
 A: This is the problem of finding not-necessary-linear codes in a Hamming cube: for odd dimensions, one could take this table as a lower bound.
EDIT: The Hoffman bound gives a better bound that Fedor Petrov's for even $n$:
The Hoffman bound for a regular graph is $\alpha \leq |V|* \frac{-\lambda}{d-\lambda}$, where $\lambda$ is the smallest eigenvalue of the graph, and $d$ is the degree of the graph.
In order to compute the smallest eigenvalue, we can apply the character formula for Cayley graphs of abelian groups: in this case, the eigevalues are simply $\sum_{s}\prod_a{s_a}$, where $s$ ranges over all codewords with 1 or 2 $-1$s (the remaining bits are $1$), and $a$ some subset of indicies. 
As $s$ is invariant with bit permutation, only the size of  $a$ matter. Let $w$ denote the size of $a$. The corresponding eigenvalue is $2w^2 - 2wn - 2w + \frac{n^2+n}2$, and attains its minimum at $w=\frac{n}2$ and $w=\frac{n}2+1$, where the value is $-\frac{n}2$. 
The upper bound is therefore $\frac{2^n}{n+2}$. In odd dimensions the reasoning applies too, but the bound is the same of Fedor Petrov's.
A: The upper bound is $2^n/(n+1)$ coming from the observation that 1-neighborhoods of red vertices must be disjoint. Sometimes it is tight, say, Hamming codes give an example of exactly $2^n/(n+1)$ red vertices for $n=2^k$. To do it, identify $n$ coordinates with the set $A$ of all vertices of $k$-dimensional cube $\{0,1\}^n$ except the origin $(0,0,\dots,0)$, and call the functions from $A$ to $\mathbb{F}_2$ red if it sums up to 0 on every facet $\{x_i=1\}$ for all $i=1,2,\dots,k$. We get exactly $2^{n-k}=2^n/(n+1)$ red functions and any two of them differ at least in three vertices. Indeed, if red functions $f,g$ differ in at most two vertices $u,v\in A$, then there exists $i$ such that $u_i=1$ and $v_i=0$, and one of the functions $f,g$ has odd sum on the facet $\{x_i=1\}$.
