most recent 30 from http://mathoverflow.net 2013-05-22T15:00:31Z http://mathoverflow.net/feeds/question/111626 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/111626/how-many-non-overlapping-k-hop-neighborhoods-can-be-uniquely-colored-on-an-n-di StoicPorpoise 2012-11-06T08:53:33Z 2012-11-20T13:22:00Z

<p>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? </p> <p>Is an optimal solution for $Q$, or a tight bound known for certain values of $k$? </p> <p>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.</p>

http://mathoverflow.net/questions/111626/how-many-non-overlapping-k-hop-neighborhoods-can-be-uniquely-colored-on-an-n-di/111636#111636 Ben Barber 2012-11-06T12:40:28Z 2012-11-06T12:40:28Z

<p>This is a fundamental question in coding theory, and is open in general. The Wikipedia page on <a href="http://en.wikipedia.org/wiki/Block_code" rel="nofollow">block codes</a> has lots of possible hooks into the area.</p>