Skip to main content
2 of 6
added 317 characters in body; added 66 characters in body; added 1 characters in body

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 optimum 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$.