1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
3
  • $\begingroup$ Perhaps someone more familiar with codes can provide more specific recommendations for useful reading? $\endgroup$
    – Ben Barber
    Nov 6, 2012 at 12:41
  • $\begingroup$ @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? $\endgroup$ Nov 6, 2012 at 12:45
  • $\begingroup$ "Is there a known time complexity..." Actually, you just said the problem was open, didn't you? Sorry. $\endgroup$ Nov 6, 2012 at 12:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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