# 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.

• Isn't the independence number of the union of the squared graph and itself? – LeechLattice Feb 15 '19 at 11:33
• @Bullet51 it is, but how does it help? – Fedor Petrov Feb 15 '19 at 11:34
• If you write the coordinates of the vertices of the $n$-d hypercube, these are the $n$-letter words on the alphabet $0,1$. The distance between two vertices is exactly the number of distinct letters. – quarague Feb 15 '19 at 11:35
• One could use independence number bounds, like Lovasz $\theta$ bound, Hoffman $\lambda_1$ bound, etc. – LeechLattice Feb 15 '19 at 11:36
• Just as some additional information, I found the following data through brute force: n:r, where r is the maximum number of nodes: 2:1 3:2 4:2 5:4 6:8 – user135868 Feb 15 '19 at 11:39

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.

• I think, the estimate $2^n/(n+2)$ for even $n$ may be obtained also elementary (without eigenvalues) as follows. If we have $k$ centers of disjoint 1-balls, for each center $p$ there exist at least $n/2$ points on distance 2 from $p$ not covered by these balls (say, if $p=0$, by parity reasoning for each $i$ there exists $j\ne i$ such that the vertex $e_i+e_j$ is not covered). And each such point corresponds to at most $n/2$ centers, therefore there exist at least $k$ not covered points and we get $2^n- k(n+1)\geqslant k$. – Fedor Petrov Feb 18 '19 at 9:00

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\}$$.

• This predicts that in the case n=4, the upper bound should be 16/5, which would mean three red nodes can be placed. I know empirically that only two can be fit on this kind of graph. – user135868 Feb 15 '19 at 12:14
• @Grothendeeeeck The Lovasz $\theta$ bound gives $n \leq 8/3$ in this case, which proves the optimality of the number of vertices. – LeechLattice Feb 15 '19 at 12:22
• @Bullet51 I'm terribly sorry but I don't know what the Lovasz 𝜃 bound is. Could you recommend a simple source to learn about it from, or else give a quick explanation yourself? – user135868 Feb 15 '19 at 12:33
• @Grothendeeeeck en.wikipedia.org/wiki/Lov%C3%A1sz_number – LeechLattice Feb 15 '19 at 12:34
• @Bullet51 Hahahaha that's still a bit out of my league it's alright I'll figure it out – user135868 Feb 15 '19 at 12:38