# How many non-overlapping k-hop neighborhoods can be uniquely colored on an $N$-dimensional hypercube?

Imagine I have a $N$-dimensional hypercube. My aim is to distinctly color as many non-overlapping $k$-hop neighborhoods as possible (i.e. sets of vertices connected by a Manhattan distance of at most $k$). What is the maximum number of non-overlapping neighborhoods, $Q$, that can be distinctly colored?

Is an optimal solution for $Q$, or a tight bound known for certain values of $k$?

Motivation: It is my understanding (which may be in error) that if we set $k =$ Ceiling[$\frac{d}{2}$], then $Q$ is the maximum size of a family of strings have a pairwise Hamming distance greater than $d$. I imagine this can be abstracted to larger alphabet sizes $q>2$ (i.e. $(N,q)$ Grey codes). If this is wrong, please do let me know.

-

This is a fundamental question in coding theory, and is open in general. The Wikipedia page on block codes has lots of possible hooks into the area.

-
Perhaps someone more familiar with codes can provide more specific recommendations for useful reading? –  Ben Barber Nov 6 '12 at 12:41
@Ben Barber Yeah, that's sort of what I thought. However, it would be great to have a reference explicitly stating that this is an open problem? Is there a known time complexity for the problem of finding the maximum number of non-overlapping subgraphs in the problem description? –  StoicPorpoise Nov 6 '12 at 12:45
"Is there a known time complexity..." Actually, you just said the problem was open, didn't you? Sorry. –  StoicPorpoise Nov 6 '12 at 12:57