MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.