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.



Packing vertices on a hypercube graph?
This is the problem of finding not-necessary-linear codes in a Hamming cube: for odd dimensions, one could take [this table](https://www.eng.tau.ac.il/~litsyn/tableand/index.html#dist3) 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.


