Happy holidays, folks! And happy birthday to Topological Musings, which Vishal started just a little over a year ago — we’ve both had a really good time with it.
And in particular with the Problem of the Week series. Which, as we all know, doesn’t come out every week — but then again, to pinch a line from John Baez’s This Week’s Finds, we never said it would: only that each time a new problem comes out, it’s always the problem for that week! Anyway, we’ve been very gratified by the response and by the ingenious solutions we routinely receive — please keep ‘em coming.
This problem comes courtesy of regular problem-solver Arin Chaudhuri and — I’ll freely admit — this one defeated me. I didn’t feel a bit bad though when Arin revealed his very elegant solution, and I’d like to see what our readers come up with. Here it is:
What is the maximum number of colors you could use to color the vertices of an 8-dimensional cube, so that starting from any vertex, each color occurs as the color of some neighbor of that vertex? (Call two vertices neighbors if they are the two endpoints of an edge of the cube.)
Arin, Vishal, and I would be interested and pleased if someone solved this problem for all dimensions 
Please submit solutions to topological[dot]musings[At]gmail[dot]com by Friday, January 2, 2009, 11:59 pm (UTC); do not submit solutions in Comments. Everyone with a correct solution will be inducted into our Hall of Fame! We look forward to your response.
4 comments
Comments feed for this article
December 27, 2008 at 3:12 am
Rod Carvalho
Todd,
IMHO, the problem statement is a bit sketchy. The problem sounds quite interesting, but I don’t get what exactly is being asked.
The only thing I understood is that we have an
-dimensional cube whose vertices we would like to color with 
colors. We would like to maximize 
given the constraint that the colors of a vertex and the colors of its neighbors obey some conditions. I don’t understand what the conditions are.
Could you please, pleeeease rephrase the problem in rigorous terms? Many thanks in advance.
December 27, 2008 at 4:18 am
Todd Trimble
I honestly thought it was rigorously stated (and I fancy myself as generally pretty careful when I discuss mathematics). But I’ll say it more formally now:
Let
be a set whose elements we’ll call “colors”. An 
-coloring of a set 
is a function 
. Let 
now be the set of vertices of an 8-dimensional cube, and define the neighborhood relation 
by 
if and only if 
and 
are distinct and there exists an edge of the cube that both 
and 
are incident to.
Now consider the following condition on a coloring
:
What is the maximal cardinality of a set
for which there exists a coloring 
satisfying this condition?
Let me know if the problem is still unclear.
December 27, 2008 at 4:32 am
Rod Carvalho
Todd,
I didn’t mean to offend anyone. I just found the original problem statement slightly ambiguous. It would have been silly to dedicate some of my time to solving a problem which is not the one you proposed. Now that you’ve written the problem statement formally, all ambiguity has been removed. Thanks.
December 27, 2008 at 4:41 am
Todd Trimble
No offense taken. I’ll concede that the problem statement was tersely put, so it’s probably good that you asked.