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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Perhaps someone more familiar with codes can provide more specific recommendations for useful reading? $\endgroup$
    – Ben Barber
    Commented 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$
    – StoicPorpoise
    Commented 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$
    – StoicPorpoise
    Commented Nov 6, 2012 at 12:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .