MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

6 edited body

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

5 added 26 characters in body

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$. q>2$(i.e.$(N,q)$Grey codes). If this is wrong, please do let me know. 4 added 42 characters in body 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\$. If this is wrong, please do let me know.

3 edited tags